大规模社交网络社区发现及可视化算法

An Algorithm for Large-scale Social Network Community Detection and Visualization

针对现有社区发现算法存在社区质量不满足图可视化要求和算法效率低的问题,提出一种改进的启发式社区发现算法.该算法基于模块度优化,通过结合预先选取种子节点的方法,抑制算法中大社区的过度合并,同时及时合并小的社区;然后针对力导引布局算法存在社区结构不明显和布局效率低问题,提出一种展示大规模社区结构的社区布局算法,通过引入社区引力促使同一社区中的节点聚拢,优化了社区引力建模,简化了布局算法步骤.实验结果表明,文中算法能够清晰、高效地展示大规模社交网络数据.

The existing community detection algorithms are inefficient and can’t satisfy the requirements of graph visualization. Aiming at these problems, two improved heuristic algorithms based on modularity optimization are proposed. This first algorithm uses the method of selecting seed nodes in advance to inhibit the excessive merger of the large community in the Louvain algorithm, and timely merges small communities aswell. In addition, since current force-directed algorithms have less obvious community structure and low efficiency,a community layout algorithm for showing large-scale social network community structure is proposed.By using community gravitational force to prompt nodes of the same community together, the second algorithm optimizes community gravity model, and simplifies the algorithm steps too. The experimental results show that the above two algorithms working together can show the massive social network data clearly and effectively.