基于社团划分的网络聚类布局算法

doi:10.3969/j.issn.1006-2475.2017.12.001

计算机与现代化

• 算法设计与分析 • 下一篇

基于社团划分的网络聚类布局算法

(1.中国科学院电子学研究所,北京100190；2.中国科学院大学,北京100039)

收稿日期:2017-04-17 出版日期:2017-12-25 发布日期:2017-12-26
作者简介:周弦(1992-),女,安徽合肥人,中国科学院大学电子学研究所硕士研究生，研究方向：数据可视化；黄廷磊(1971-),男,博士生导师,博士,研究方向：数据挖掘，大数据分析；梁霄(1981-),男,讲师,博士,研究方向：复杂网络，知识工程。
基金资助:
国家高技术研究发展计划项目（2015AA7115028，2015AA7115061）

Network Clustering Layout Algorithm Based on Detecting Community Structure

(1. Institute of Electronics, Chinese Academy of Sciences, Beijing 100190, China； 2. University of Chinese Academy of Sciences, Beijing 100039, China)

Received:2017-04-17 Online:2017-12-25 Published:2017-12-26

摘要/Abstract

摘要： 复杂网络日益受到广大专家和学者们的关注，对其进行可视化展示可以帮助用户发现复杂网络表征的复杂系统中隐藏的知识信息，对计算机科学、社会学、生物学等领域具有重要的意义。力导引布局算法是复杂网络可视化领域的主流算法，它用节点连接图的形式对复杂网络进行抽象表示，布局遵循一定的美学标准如节点的均匀分布、边长尽量一致等，这在一定程度上阻碍了对复杂网络的社团结构的展示。针对以上问题，本文提出引入基于度中心性的社团斥力与引力对力导引算法进行改进，以对复杂网络进行聚类布局。实验结果表明，本文算法可有效地展示复杂网络的社团结构，同时又能保留社团之间边缘节点的信息。

关键词: 社团结构, 力导引布局, 度中心性, 聚类布局

Abstract: The complex network is becoming increasingly concerned by the experts and scholars. The visualization of the complex network can help the users to discover the hidden knowledge and information in the complex system represented by complex network, which is of great significance to the fields of computer science, sociology, and biology. The force-directed layout algorithm is the mainstream algorithm in the field of complex network visualization. It uses the form of node connection graph to abstract the complex network, the layout follows aesthetic standards such as the uniform distribution of nodes and the uniform of edges, to a certain extent, which hinders the display of the community structure of complex networks. Aiming at above problems, this paper introduces the repulsion and gravitational force of the community based on the degree centrality to improve the clustering layout of the complex network. The experimental results show that the proposed algorithm can effectively display the community structure of complex networks while preserving the information of margin nodes between communities.

Key words: community structure, force-directed layout, degree centrality, clustering layout

中图分类号:

TP391.1

周弦1,2，黄廷磊1，梁霄1. 基于社团划分的网络聚类布局算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2017.12.001.

ZHOU Xian1,2, HUANG Ting-lei1, LIANG Xiao1. Network Clustering Layout Algorithm Based on Detecting Community Structure[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.12.001.

参考文献

［1］Newman M E J. The structure and function of complex networks［J］. SIAM Review, 2003,45(2):167-256. ［2］Newman M E J, Peixoto T P. Generalized communities in networks［J］. Physical Review Letters, 2015,115(8):088701. ［3］耿文静,吴渝. 可视化技术及其在复杂网络上的研究与应用现状［J］. 数字通信, 2012,39(4):27-33. ［4］Eades P A. A heuristic for graph drawing［J］. Congressus Numerantium, 1984,42(42):149-160. ［5］Kamada T, Kawai S. An algorithm for drawing general undirected graphs［J］. Information Processing Letters, 1989,31(1):7-15. ［6］Fruchterman T M J, Reingold E M. Graph drawing by force-directed placement［J］. Software Practice & Experience, 1991,21(11):1129-1164. ［7］Noack A. Energy models for graph clustering［J］. Journal of Graph Algorithms & Applications, 2007,11(2):453-480. ［8］Frick A, Ludwig A, Mehldau H. A fast adaptive layout algorithm for undirected graphs (extended abstract and system demonstration)［C］// International Symposium on Graph Drawing. 1994:388-403. ［9］Bannister M J, Eppstein D, Goodrich M T, et al. Force-directed graph drawing using social gravity and scaling［C］// Proceedings of the 20th International Conference on Graph Drawing. 2012:414-425. ［10］Gibson H, Faith J. Node-attribute graph layout for small-world networks［C］ // 2011 15th International Conference on Information Visualization (IV). 2011:482-487. ［11］Tulip. Better Visualization Through Research［EB/OL］. http://tulip.labri.fr/, 2017-04-10. ［12］GNU. The Prefuse Visualization Toolkit［EB/OL］. http://www.prefuse.org, 2017-04-10. ［13］Gephi. The Open Graph viz Platform［EB/OL］. http://gephi.org, 2017-04-10. ［14］Graphviz. Graphviz-graph Visualization Software［EB/OL］. http://www.graphviz.org, 2017-04-10. ［15］Huang Weidong, Eades P, Hong S, et al. Improving multiple aesthetics produces better graph drawings［J］. Journal of Visual Languages & Computing, 2013,24(4):262-272. ［16］任晓龙,吕琳媛. 网络重要节点排序方法综述［J］. 科学通报, 2014,59(13):1175-1197. ［17］Chen Duanbing, Lu Linyuan, Shang Mingsheng, et al. Identifying influential nodes in complex networks［J］. Physical A: Statistical Mechanics and Its Applications, 2012,391(4):1777-1787. ［18］Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations［J］. Behavioral Ecology and Sociobiology, 2003,54(4):396-405. ［19］Girvan M, Newman M E J. Community structure in social and biological networks［J］. Proceedings of the National Academy of Sciences, 2002,99(12):7821-7826. ［20］White J G, Southgate E, Thomson J N, et al. The structure of the nervous system of the nematode caenorhabditis elegans［J］. Philos Trans R Soc Lond B Biol Sci., 1986,314(1165):1-340. ［21］朱志良,林森,崔坤,等. 基于复杂网络社区划分的网络拓扑结构可视化布局算法［J］. 计算机辅助设计与图形学学报, 2011,23(11):1808-1815. ［22］李卓远,吴为民,洪先龙. 优化线长和拥挤度的增量式布局算法［J］. 计算机辅助设计与图形学学报, 2003,15(6):651-655. ［23］Lin Chun-cheng,Yen Hsu-chun. A new force-directed graph drawing method based on edge-edge repulsion［J］. Journal of Visual Languages & Computing, 2012,23(1):29-42.

基于社团划分的网络聚类布局算法

Network Clustering Layout Algorithm Based on Detecting Community Structure

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价