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

发布时间：2018-04-25 20:04

本文选题：矩阵的谱 + 拉普拉斯矩阵　；参考：《计算机应用与软件》2013年02期

【摘要】：网络的代数连通性是拉普拉斯矩阵的第二小特征值,它可以用于测量网络的连通程度。为改善复杂网络分割算法的时间复杂度,基于代数连通性提出一种谱优化模型,并将其应用于复杂网络的小社区发现中。通过最小化网络连通性函数在候选边集中选择要删除的边集。该凸优化问题可由半正定规划解决,但其时间复杂度高,所以只能处理规模适中的复杂网络。为解决这个模型优化问题,采用贪婪策略优化方法,使该算法可以应用于大规模复杂网络。另一方面,社区边界的边影响代数连通性函数的优化效果,根据费德勒向量为每条边设定权重来解决这一问题。最后应用该模型对模拟复杂网络和真实复杂网络实例进行验证,结果表明该模型有效降低了GN算法的迭代次数,从而降低其时间复杂度,并有效保持其分割效果。
[Abstract]:The algebraic connectivity of the network is the second smallest eigenvalue of the Laplace matrix, which can be used to measure the connectivity of the network. In order to improve the time complexity of complex network segmentation algorithm, a spectral optimization model based on algebraic connectivity is proposed and applied to small community discovery of complex networks. By minimizing the network connectivity function, the edge set to be deleted is selected in the candidate edge set. The convex optimization problem can be solved by positive semidefinite programming, but its time complexity is high, so it can only deal with moderate scale complex networks. In order to solve the model optimization problem, the greedy strategy optimization method is adopted to make the algorithm applicable to large-scale complex networks. On the other hand, the edge of community boundary affects the optimization effect of algebraic connectivity function. According to Federer vector, the weight of each edge is set to solve this problem. Finally, the model is used to verify the simulation of complex networks and real complex networks. The results show that the model can effectively reduce the number of iterations of GN algorithm, thus reduce its time complexity, and effectively maintain its segmentation effect.
【作者单位】：天津大学计算机科学与技术学院;天津财经大学计算机科学与技术学院;
【基金】：国家教育部人文社科青年基金项目(08JC870008)
【分类号】：TP393.09;TP301.6

【相似文献】