Journal of Software, Vol 6, No 8 (2011), 1545-1553, Aug 2011
doi:10.4304/jsw.6.8.1545-1553

A New Vertex Similarity Metric for Community Discovery: a Local Flow Model

Yueping Li, Yunming Ye, Xiaolin Du

Abstract


The hierarchy clustering methods based on vertex similarity have the advantage that global evaluation can be incorporated for community discovery. Vertex similarity metric is the most important part of these methods. However, the existing methods perform not well for community discovery compared with the state-of-the-art algorithms. In this paper, we propose a new vertex similarity metric based on local flow model, called Local Flow Metric (LFM), for community discovery. LFM considers both the number of connecting paths and local edge density which are essential measures in community structure. Compared with the existing metrics of vertex similarity, LFM outperforms substantially in community discovery quality and the computing time. Furthermore, our LFM algorithm is superior to the state-of-the-art algorithms in some aspects.


Keywords


hierarchy clustering; vertex similarity; community discovery; network flow

References


A. Clauset, C. Moore, and M.E.J. Newman, “Hierarchical structure and the prediction of missing links in networks,” Nature, vol. 453, pp. 98–101, 2008.
http://dx.doi.org/10.1038/nature06830
PMid:18451861

D. Price, “Networks of scientific papers,” In M. Kochen(Ed.), the growth of knowledge: readings on organization and retrieval of information, New York: Wiley, 1965, pp. 145–155.

J. A. Dunne, R. J. Williams, and N. D. Martinez, “Foodweb structure and network theory: The role of connectance and size,” Proc. Natl. Acad. Sci. USA, vol. 99, pp. 12917–12922, 2002.
http://dx.doi.org/10.1073/pnas.192407699
PMid:12235364    PMCid:130560

S. A. Kauffman, “Metabolic stability and epigenesis in randomly connected nets,” J. Theor. Bio., vol. 22, pp. 437–467, 1969.
http://dx.doi.org/10.1016/0022-5193(69)90015-0

T. Ito, T. Chiba, R. Ozawa, M. Yoshida, M. Hattori, and Y. Sakaki, “A comprehensive two-hybrid analysis to explore the yeast protein interactome,” Proc. Natl. Acad. Sci. USA, vol. 98, pp. 4569–4574, 2001.
http://dx.doi.org/10.1073/pnas.061034498
PMid:11283351    PMCid:31875

M. Sales-Pardo, R. Guimera, A.A. Moreira, and L.A.N. Amaral, “Extracting the hierarchicial structure of complex system,” Proc. Natl. Acad. Sci. USA, vol. 104, pp. 15224– 15229, 2007.
http://dx.doi.org/10.1073/pnas.0703740104
PMid:17881571    PMCid:2000510

B.W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell System Technical Journal, vol. 49, pp. 291–308, 1970.

M. Fiedler, “Algebraic connectivity of graphs,” Czech. Math. J., vol. 23, pp. 298–305, 1973.

A. Pothen, H. Simon, and K.-P. Liou, “Partitioning sparse matrices with eigenvectors of graphs,” SIAM J. Matrix Anal. Appl., vol. 11, pp. 430–452, 1990.
http://dx.doi.org/10.1137/0611030

J. Scott, Social Network Analysis: A Handbook. Sage, London, 2nd edition, 2000.

L. Donetti, and M. A. Munoz, “Detecting network communities: a new systematic and powerful algorithm,” J. Stat. Mech., P10012, 2004. A. Capocci, V.D.P. Servedio, G. Caldarelli, and F. Colaiori, “Detecting communities in larger networks,” Physica A, vol. 352, pp. 669, 2005.
http://dx.doi.org/10.1016/j.physa.2004.12.050

N. Alves, “Unveiling community structures in weighted networks,” Phys. Rev. E, vol. 76, 036101, 2007.

J. Reichardt and S. Bornholdt, “Detecting fuzzy community sturctures in complex networks with a Potts model,” Phys. Rev. Lett, vol. 93, 218701, 2004.

H. Zhou, “Distance, dissimilarity index, and network community structure,” Phys. Rev. E, vol. 67, 061901, 2003.

A. Arenas, A. Diaz-Guilera, and C. J. Peerez-Vicente, “Synchronization reveals topological scalses in complex networks,” Phys. Rev. Lett, vol. 96, 114102, 2006.

S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, pp. 75-174, 2010.
http://dx.doi.org/10.1016/j.physrep.2009.11.002

M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl. Acad. Sci. USA, vol. 99, 7821–7826, 2002.
http://dx.doi.org/10.1073/pnas.122653799
PMid:12060727    PMCid:122977

A. Clauset, M. E. J. Newman, and C. Moore, “Finding community structure in very large networks,” Phys. Rev. E, vol. 70, 066111, 2004.

M. E. J. Newman, “Detecting community structure in networks,” Eur. Phys. J. B, vol. 38, pp. 321–330, 2004.
http://dx.doi.org/10.1140/epjb/e2004-00124-y

M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E, vol. 69, 026113, 2004.

A. Clauset, “Finding local community structure in networks,” Phys. Rev. E, vol. 72, 026132, 2005.

R. Duda, P. Hart, D. Stork, Pattern Recognition, 2nd Edition, John Wiley and Sons, 2003.

E. Ravasz and A.L. Barabási, “Hierarchical organization in complex network,” Phys. Rev. E, vol. 67, 026112, 2003.

E. Ravasz, A.L. Somera, D.A. Mongru, Z.N. Oltvai, and A.L. Barabási, “Hierarchical organization of modularity in metabolic networks,” Science, vol. 297, pp. 1551–1555, 2002.
http://dx.doi.org/10.1126/science.1073374
PMid:12202830

D. Lusseau, K. Schneider, O.J. Boisseau, P. Haase, E. Slooten, and S.M. Dawson, “The bottlenose dolphin commu-nity of doubful sound features a large problem of long-lasting associations,” Behav. Ecol. Sociobiol., vol. 54 pp. 396–405, 2003.
http://dx.doi.org/10.1007/s00265-003-0651-y


Full Text: PDF


Journal of Software (JSW, ISSN 1796-217X)

Copyright @ 2006-2012 by ACADEMY PUBLISHER – All rights reserved.