Detecting Communities of Complex Networks Based on Dependence Degree of Two Nodes

Computer and Modernization ›› 2014, Vol. 0 ›› Issue (4): 109-112.

Previous Articles Next Articles

Detecting Communities of Complex Networks Based on Dependence Degree of Two Nodes

1. Department of Basic, Langfang Polytechnic Institute, Langfang 065000, China;


2. College of Science, Hebei University of Technology, Tianjin 300401, China

Received:2013-12-23 Online:2014-04-17 Published:2014-04-23

Abstract

Abstract:

Abstract: Detecting community structure in complex networks is significant in understanding the structures and functions of networks. The dependence degree of two nodes is analyzed, and a new standard is found for whether a node is belonging to the community. An initial community is first constructed from a node with maximal node strength and its neighbors which satisfying the dependence degree quantitative condition, then the initial community is expanded by adding nodes according to some quantitative conditions. Only local information of nodes is need to use, so the time complexity is a linear complexity. It is applied to the classic Zachary network to verify the validity.

Key words:

Key words: complex network； community structures； dependence degree of two nodes； quantitative condition, local algorithm

CLC Number:

TP301.6

GAO Hongwei1, XU Yong2. Detecting Communities of Complex Networks Based on Dependence Degree of Two Nodes[J]. Computer and Modernization, 2014, 0(4): 109-112.

References

［1］

汪小帆,李翔,陈关荣. 复杂网络理论及其应用［M］. 北京:清华大学出版社, 2006.〖LL〗

［2］ Girvan M, Newman M E J. Community structure in social and biological networks［J］. Proc.Natl.Acad.Sci., 2002,99(12):78217826.

［3］ Ravasz E, Somera A L, Mongru D A, et al. Hierarchical organization of modularity in metabolic networks［J］. Science, 2002,297(5586):15511555.

［4］ Flake G W, Lawrence S R, Giles C L, et al. Selforganization and identification of Web communities［J］. IEEE Computer, 2002,35(3):6670.

［5］ Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs［J］. Bell Labs Technical Journal, 1970,49(2):291307.

［6］ Fiedler M. Algebraic connectivity of graphs［J］. Czechoslovak Mathematical Journal, 1973,23(2):298305.

［7］ Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs［J］. SIAM Journal on Matrix Analysis and Applications Archive, 1990,11(3):430452. 

［8］〖KG-*4〗Newman M E J. Fast algorithm for detecting community structure in networks［J］. Phys.Rev.E, 2004,69(6):15. 

［9］解,汪小帆. 复杂网络的一种快速局部社团划分算法［J］. 计算机仿真， 2007,24(11):8285.

［10］赵晓慧,刘微. 基于局部信息的复杂网络社团结构发现算法［J］. 微型机与应用, 2011，30(15):4346.

［11］Barabási A L， Albert R. Emergence of scaling in random networks［J］. Science, 1999,286(5439):509512.

［12］Wang X T, Chen G R, Lu H T. A very fast algorithm for detecting community structures in complex networks［J］. Physica A, 2007,384(2):667674.

［13］Zachary W W. An information flow model for conflict and fission in small groups［J］. Journal of Anthropological Research, 1977,33(4):452473.

Detecting Communities of Complex Networks Based on Dependence Degree of Two Nodes

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments