A weight's agglomerative method for detecting communities in weighted networks based on weight's similarity

doi:10.1088/1674-1056/20/4/040511

Abstract This paper proposes the new definition of the community structure of the weighted networks that groups of nodes in which the edge's weights distribute uniformly but at random between them. It can describe the steady connections between nodes or some similarity between nodes' functions effectively. In order to detect the community structure efficiently, a threshold coefficient $\kappa$ to evaluate the equivalence of edges' weights and a new weighted modularity based on the weight's similarity are proposed. Then, constructing the weighted matrix and using the agglomerative mechanism, it presents a weight's agglomerative method based on optimizing the modularity to detect communities. For a network with n nodes, the algorithm can detect the community structure in time O(n²log₂ⁿ). Simulations on networks show that the algorithm has higher accuracy and precision than the existing techniques. Furthermore, with the change of $\kappa$ the algorithm discovers a special hierarchical organization which can describe the various steady connections between nodes in groups.

Keywords: complex networks weight's similarity community structure weight's agglomerative method

Received: 28 August 2010
Revised: 27 October 2010
Accepted manuscript online:

PACS:	05.45.Xt	(Synchronization; coupled oscillators)
	89.75.Hc	(Networks and genealogical trees)

Fund: Project supported by the Fundamental Research Funds for the Central Universities (Grant Nos. KYZ200916, KYZ200919 and KYZ201005) and the Youth Sci-Tech Innovation Fund, Nanjing Agricultural University (Grant No. KJ2010024).

Cite this article:

Shen Yi(沈毅) A weight's agglomerative method for detecting communities in weighted networks based on weight's similarity 2011 Chin. Phys. B 20 040511

[1]	Albert R, Jeong H and Barabási A L 1999 Nature 401 130
[2]	Ra'ul P O, Julio S, Ana P and José A G 2009 Comput. Commun. 32 1118
[3]	Newman M E J 2001 Proc. Natl. Acad. Sci. USA 98 404
[4]	Watts D J and Strogatz S H 1998 Nature 393 440
[5]	Redner S 1998 Euro. Phys. J. B 4 131
[6]	Danon L, Duch J and Guilera A D 2005 J. Stat. Mech. P09008
[7]	Girvan M and Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821
[8]	Newman M E J and Girvan M 2004 Phys. Rev. E 69 026113
[9]	Newman M E J 2006 Proc. Natl. Acad. Sci. USA 103 8577
[10]	Lancichinetti A and Fortunatol S 2009 Phys. Rev. E 80 056117
[11]	Bian Q X and Yao H X 2010 Acta Phys. Sin. 59 3027 (in Chinese)
[12]	Pu C L and Pei W J 2010 Acta Phys. Sin. 59 3841 (in Chinese)
[13]	Meng Q K and Zhu J Y 2009 Chin. Phys. B 18 3632
[14]	Liu M X and Ruan J 2009 Chin. Phys. B 18 2115
[15]	Estrada E 2006 Euro. Phys. J. B 52 563
[16]	Song Y R and Jiang G P 2009 Acta Phys. Sin. 58 5911 (in Chinese)
[17]	Hu K, Hu T and Tang Y 2010 Chin. Phys. B 19 080206
[18]	Lü L and Zhang C 2009 Acta Phys. Sin. 58 1462 (in Chinese)
[19]	Li Z Y, Xie Z W, Chen T and Ouyang Q 2009 Chin. Phys. B 18 5544
[20]	Wang X H, Jiao L C and Wu J S 2010 Chin. Phys. B 19 020501
[21]	Jin X Z 2010 Chin. Phys. B 19 080508
[22]	Bernardo M D, Garofalo F and Sorrentino F 2007 Int. J. Bifur. Chaos 17 3499
[23]	Wu X J and Lu H T 2010 Chin. Phys. B 19 070511
[24]	Onnela J P, Saramaki J, Kertesz J and Kaski K 2005 Phys. Rev. E 71 065103
[25]	Chen W D, Xu H and Guo Q 2010 Acta Phys. Sin. 59 4514 (in Chinese)
[26]	Newman M E J 2004 Phys. Rev. E 70 056131
[27]	Alves N A 2007 Phys. Rev. E 76 036101
[28]	Fan Y, Li M, Zhang P, Wu J S and Di Z R 2006 Physica A 370 869
[29]	Duch J and Arenas A 2005 Phys. Rev. E 72 027104
[30]	Grossman R 2009 IT Professional 11 23
[31]	Frank K A 1996 Soc. Networks 18 93 endfootnotesize

[1]	Analysis of cut vertex in the control of complex networks Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Chin. Phys. B, 2023, 32(2): 028902.
[2]	Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Chin. Phys. B, 2023, 32(1): 018903.
[3]	Characteristics of vapor based on complex networks in China Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Chin. Phys. B, 2022, 31(4): 049201.
[4]	Robust H_∞ state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Chin. Phys. B, 2022, 31(2): 020503.
[5]	Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Chin. Phys. B, 2022, 31(10): 100504.
[6]	LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). Chin. Phys. B, 2021, 30(8): 088901.
[7]	Complex network perspective on modelling chaotic systems via machine learning Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Chin. Phys. B, 2021, 30(6): 060506.
[8]	Exploring individuals' effective preventive measures against epidemics through reinforcement learning Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni (倪顺江), and Shi-Fei Shen(申世飞). Chin. Phys. B, 2021, 30(4): 048901.
[9]	Influential nodes identification in complex networks based on global and local information Yuan-Zhi Yang(杨远志), Min Hu(胡敏), Tai-Yu Huang(黄泰愚). Chin. Phys. B, 2020, 29(8): 088903.
[10]	Identifying influential spreaders in complex networks based on entropy weight method and gravity law Xiao-Li Yan(闫小丽), Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni(倪顺江). Chin. Phys. B, 2020, 29(4): 048902.
[11]	Modeling and analysis of the ocean dynamic with Gaussian complex network Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇)†, Christian B\"ohm, and Xueen Chen(陈学恩). Chin. Phys. B, 2020, 29(10): 108901.
[12]	Pyramid scheme model for consumption rebate frauds Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[13]	Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms Shi-Zhao Zhu(朱世钊), Yu-Qing Wang(王玉青), Bing-Hong Wang(汪秉宏). Chin. Phys. B, 2019, 28(10): 108901.
[14]	Coordinated chaos control of urban expressway based on synchronization of complex networks Ming-bao Pang(庞明宝), Yu-man Huang(黄玉满). Chin. Phys. B, 2018, 27(11): 118902.
[15]	Detecting overlapping communities based on vital nodes in complex networks Xingyuan Wang(王兴元), Yu Wang(王宇), Xiaomeng Qin(秦小蒙), Rui Li(李睿), Justine Eustace. Chin. Phys. B, 2018, 27(10): 100504.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

A weight's agglomerative method for detecting communities in weighted networks based on weight's similarity

Cite this article:

Online attention