基于复杂网络结构的社区划分算法研究

作     者：徐宝成 

作者单位：哈尔滨工程大学 

学位级别：硕士

导师姓名：刘杰

授予年度：2018年

学科分类：07[理学] 08[工学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

主      题：复杂网络 社区划分 电阻网络 电压均值 

摘      要：随着科技的不断进步,现实世界中复杂系统的种类和规模都在不断发生变化,种类的多样化与规模的迅速增长使复杂网络的复杂性变得越来越高,如何在这种巨大的数据量中获得有用知识成为复杂网络研究的热点。社区划分能够揭示现实世界中存在的潜在规律,可以应用于社交网络、万维网、电子商务领域和刑侦等各个领域中。因此,本课题的研究具有理论价值和实际意义。基于电阻网络的社区划分算法能够在线性时间内对社会网络进行社区划分。然而,该类算法采用图分割的思想只能将社会网络划分为两个相似规模的社区,对多社区划分问题需要迭代执行该算法,算法执行效率比较低;此外,该类算法需要事先设置电压阈值来对社会网络进行社区划分,设定的阈值会直接影响社区划分的准确性。针对该类算法存在的上述两类问题,本文提出了一种基于电压均值的社区划分算法,使用节点电压均值选取社区中心节点,避免了电压阈值的设定,并且可以进行多社区划分;另外,本文又提出了一种基于确定社区个数的社区划分算法,使用社区核心节点作为初始中心节点,解决了预先设定欲划分社区数目的问题。最后,本文采用社区划分领域中两个经典的数据集,对所提出的算法进行实验分析验证。实验结果表明,本文提出的两个算法具有良好的划分结果,在一定程度上提高了算法效率。