一种改进的模块性指标及其社群结构探测算法

doi:10.3969/j.issn.1001-2400.2010.02.033

Abstract

Abstract:

The community structure detecting strategies are one of the important research hot spots in the field of the community structure. Firstly, the basic characteristics of the network's community structure and the modularity are discussed, and then a basic algorithm framework based on the modularity for detecting the network's community structure is summarized. Secondly, based on the definition of Newman's modularity Q, a predigested modularity and the corresponding algorithm are explored. Lastly, compared with Newman's corresponding algorithms, the results of community detection for some networks, including Ucinet networks and Pajek networks, indicate that the algorithm based on the predigested modularity is effective to get the higher modularity and that the definition of the modularity can effect the results of detecting the community structure.

Key words: network, community structure, optimization

CHEN Ying-hui;DU Hai-feng;LI Shu-zhuo. Modified modularity and the corresponding community structure detecting algorithm[J].J4, 2010, 37(2): 374-379.

References

［1］ Newman M E J, Barabàsi A L, Watts D J. The Structure and Dynamic of Networks ［M］. Princeton: Princeton University Press, 2006.
［2］ Wasserman S, Faust K. Social Network Analysis: Methods and Applications ［M］. Cambridge: Cambridge University Press, 1994.
［3］ Scott J. Social Network Analysis: a Handbook ［M］. London: Sage Publications Ltd, 2002.
［4］ Newman M E J. Detecting Community Structure in Networks ［J］. The European Physical Journal B, 2004, 38(2): 321-330.
［5］ Leicht E A, Newman M E J. Community Structure in Directed Networks ［J/OL］. ［2007-09-27］. http://arxiv.org/abs/0709.4500.
［6］ Porter M A, Mucha P J, Newman M E J, et al. Community Structure in the United States House of Representatives［J/OL］. ［2007-7-19］. http://arxiv.org/abs/physics/0602033.
［7］ Guimera R, Sales-Pardo M, Lan A. Module Identification in Bipartite and Directed Networks［J/OL］. ［2007-09-07］. http://arxiv.org/abs/physics/0701151.
［8］ Arenas A, Duch J, Fernandez A, et al. Size Reduction of Complex Networks Preserving Modularity［J/OL］. ［2007-02-02］. http://arxiv.org/abs/physics/0702015.
［9］ Rosvall M, Bergstrom C T. Maps of Information Flow Reveal Community Structure in Complex Networks ［J］. Proceedings of the National Academy of Sciences of the United States of America (PNAS), 2008, 105(4): 1118-1123.
［10］ Watts D J, Strogatz S H. Collective Dynamics of Small-world Networks ［J］. Nature, 1998, 393(4): 440-442.
［11］杜海峰, 李树茁, Marcus W F, 等. 小世界网络与无标度网络的社区结构研究［J］. 物理学报, 2007, 56(12): 6886-6893.
Du Haifeng, Li Shuzhuo, Marcus W F, et al. Community Structure in Small-world and Scale-free Networks ［J］. Acta Phys Sin-Ch ed, 2007, 56(12): 6886-6893.
［12］ Newman M E J. Fast Algorithm for Detecting Community Structure in Networks ［J/OL］. ［2004-6-18］. http://prola.aps.org/abstract/PRE/v69/i6/e066133.
［13］ Mehmed K. Data Mining: Concepts, Models, Methods and Algorithms ［M］. New York: Wiley-IEEE Press, 2002.
［14］ Richard O D, Peter E H, David G S. Pattern Classification ［M］. New York: John Wiley & Sons, Inc, 2001.

[1]	HU Daiwang,JIAO Yiyuan,LI Yanni. Novel and efficient algorithm for entity relation extraction with the corpus knowledge graph [J]. Journal of Xidian University, 2021, 48(6): 75-83.
[2]	SUN Xiangang,WEI Bing,SHI Lei. Fast calculation of the reflection coefficient of the lossy symmetrical dielectric layer [J]. Journal of Xidian University, 2021, 48(6): 138-143.
[3]	LV Wenkai,YANG Pengfei,DING Yunqing,ZHANG Heyu,ZHENG Tianyang. JEDERL:A task scheduling optimization algorithm for heterogeneous computing platforms [J]. Journal of Xidian University, 2021, 48(6): 67-74.
[4]	ZHANG Yupeng,WU Zili,CHEN Ming,ZHANG Lulu. Optimization of task scheduling oriented to cross microservice chains [J]. Journal of Xidian University, 2021, 48(6): 32-39.
[5]	YU Haoyang,YIN Liang,LI Shufang,LV Shun. Recognition algorithm for the little sample radar modulation signal based on the generative adversarial network [J]. Journal of Xidian University, 2021, 48(6): 96-104.
[6]	DONG Ruchan,JIAO Licheng,ZHAO Jin,SHEN Weiyan. Application of the deep fusion mechanism in object detection of remote sensing images [J]. Journal of Xidian University, 2021, 48(5): 128-138.
[7]	LI Peng,FENG Cunqian,XU Xuguang,TANG Zixiang. Ballistic target fretting classification network based on Bayesian optimization [J]. Journal of Xidian University, 2021, 48(5): 139-148.
[8]	CHENG De,HAO Yi,ZHOU Jingyu,WANG Nannan,GAO Xinbo. Cross-modality person re-identification utilizing the hybrid two-stream neural networks [J]. Journal of Xidian University, 2021, 48(5): 190-200.
[9]	SUN Yanjing,WEI Li,ZHANG Nianlong,YUN Xiao,DONG Kaiwen,GE Min,CHENG Xiaozhou,HOU Xiaofeng. Person re-identification method combining the DD-GAN and Global feature in a coal mine [J]. Journal of Xidian University, 2021, 48(5): 201-211.
[10]	WANG Junjun,SUN Yue,LI Ying. Cloud removal method for the remote sensing image based on the GAN [J]. Journal of Xidian University, 2021, 48(5): 23-29.
[11]	DU Wenzhan,YU Zhiyong,YANG Jian,JIANG Haibin. Improved NSGA-II algorithm and research on monitoring antenna optimization deployment [J]. Journal of Xidian University, 2021, 48(5): 239-248.
[12]	YANG Jingbo,ZHAO Qijun,LYU Zejun. Synthesis of the expression image and its application under the dimentional emotion model [J]. Journal of Xidian University, 2021, 48(5): 30-37.
[13]	ZHOU Peng,YANG Jun. Semantic segmentation of remote sensing images based on neural architecture search [J]. Journal of Xidian University, 2021, 48(5): 47-57.
[14]	ZHANG Shuwei,LI Junmin. Human body detection algorithm in complex monitoring scenes [J]. Journal of Xidian University, 2021, 48(5): 68-77.
[15]	ZHAN Keyu,SUN Yue,LI Ying. Video super-resolution based on multi-scale 3D convolution [J]. Journal of Xidian University, 2021, 48(5): 8-14.

Modified modularity and the corresponding community structure detecting algorithm

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0