摘要
作为复杂网络研究的重要组成部分,社团结构分析对于理解和分析现实世界中各种社会、工程和生物等系统具有非常重要的意义.该文利用动态迭代技术,提出了一种新型的社团探测技术,能够准确而快速地识别网络中的社团结构.首先引入一种动态系统,可以使社团归属从随机状态逐步收敛到最优划分,进一步利用严格的数学分析给出了社团归属在离散时间内收敛到最优的条件.该文创新性地提出了划分指标函数的一般化形式,通过选择不同的参数,可以引申到几乎所有著名的指标函数.为了使动态系统不需要任何参数选择即可完成向最优社团的收敛,文中设计了一种新颖的图生成模型,使得算法能在无参数的情况下方便高效的运行.该算法具有较高的效率,计算复杂性分析显示算法需要的时间与稀疏网络节点的数量呈线性关系.最后,文中将算法应用到人工网络和实际网络中,结果显示算法不仅具有极高的准确性,还能够高效地应用于大规模现实网络的分析和计算中.
A feature,observable in many networks,is the presence of community structures,i.e.clusters of vertices which are densely connected to each other while less connected to the vertices outside.The community structure identification is an important problem in a wide range of applications such as marketing in social networks and study of protein interaction networks.Usually,the community members have more properties in common among themselves than with nonmembers and detecting community structure helps analyzing and searching the network with less effort.However,most existing approaches fall into the categories of either optimization based or heuristic methods which do not meet both speed and accuracy requirements simultaneously.In this paper,a new fast and accurate community detection algorithm is proposed based on dynamic system in complex networks.First,a discrete-time dynamic system is introduced to describe the assignment of community memberships,and the conditions driving the convergence of dynamics trajectory to the optimal situation are formulated.A new algorithm is proposed which can be generalized to unify the conventional algorithms widely applied.Furthermore,a new type graph generative model is designed which performs the algorithm free of the parameters.Our algorithm is highly efficient：the computational complexity analysis shows that the required time is linearly dependent on the number of all nodes in a sparse network.We perform extensivesimulations with synthetic and also real-world benchmark networks to verify the algorithmic performance.The results showed that the proposed method does not face the resolution limit problem and performs very well.
出处
《计算机学报》
EI
CSCD
北大核心
2017年第4期970-984,共15页
Chinese Journal of Computers
基金
国家自然科学基金项目(71401194
71401188
91324203
11131009)
中央财经大学"青年英才"培育支持项目(QYP1603)资助~~
关键词
社团结构
动态系统
指标函数
线性复杂度
层次结构
社交网络
community structure
dynamic system
quality function
linear time
hierarchical structure
social networks
