基于代数连通性的复杂网络社区发现研究

ON COMMUNITY DETECTION OF COMPLEX NETWORKS BASED ON ALGEBRAIC CONNECTIVITY

网络的代数连通性是拉普拉斯矩阵的第二小特征值,它可以用于测量网络的连通程度。为改善复杂网络分割算法的时间复杂度,基于代数连通性提出一种谱优化模型,并将其应用于复杂网络的小社区发现中。通过最小化网络连通性函数在候选边集中选择要删除的边集。该凸优化问题可由半正定规划解决,但其时间复杂度高,所以只能处理规模适中的复杂网络。为解决这个模型优化问题,采用贪婪策略优化方法,使该算法可以应用于大规模复杂网络。另一方面,社区边界的边影响代数连通性函数的优化效果,根据费德勒向量为每条边设定权重来解决这一问题。最后应用该模型对模拟复杂网络和真实复杂网络实例进行验证,结果表明该模型有效降低了GN算法的迭代次数,从而降低其时间复杂度,并有效保持其分割效果。

The algebraic connectivity of networks is the second smallest eigenvalue of Laplacian matrix and can be used to measure to which extent the network is connected.To meliorate the time complexity of complex network segmentation algorithm,we present a spectrum optimisation model based on algebraic connectivity and apply it in small community detection of complex networks.The model chooses the edges set to be deleted from candidate edges sets by minimizing the networks connectivity function.Though this convex optimisation problem can be solved by semi-definite program,but its high time complicity can only deal with the complex networks in moderate size.We use greedy policy optimisation approach for solving this model optimisation issue,and enable the algorithm to be able to apply to large scale complex network.On the other hand,the edges of community boundary have bad influence upon optimised result of algebraic connectivity function,so we add a weight on each edge based on Fielder vector,thus this problem is solved effectively.In test part,the model is applied to simulated complex network and real complex network for verification.The results show that the model effectively reduces the iteration times of GN algorithm,and thereby reduces its time complex as well and keeps the segmentation results effectively too.