Discovering global network communities based on local centralities

ABSTRACT

One of the central problems in studying and understanding complex networks, such as online social networks or World Wide Web, is to discover hidden, either physically (e.g., interactions or hyperlinks) or logically (e.g., profiles or semantics) well-defined topological structures. From a practical point of view, a good example of such structures would be so-called network communities. Earlier studies have introduced various formulations as well as methods for the problem of identifying or extracting communities. While each of them has pros and cons as far as the effectiveness and efficiency are concerned, almost none of them has explicitly dealt with the potential relationship between the global topological property of a network and the local property of individual nodes. In order to study this problem, this paper presents a new algorithm, called ICS, which aims to discover natural network communities by inferring from the local information of nodes inherently hidden in networks based on a new centrality, that is, clustering centrality, which is a generalization of eigenvector centrality. As compared with existing methods, our method runs efficiently with a good clustering performance. Additionally, it is insensitive to its built-in parameters and prior knowledge.

REFERENCES

• 1: Bonacich, P. F. 1972. Factoring and weighting approaches to status scores and clique identification. J. Math. Sociol. 2, 113--120.
• 2: Bonacich, P. F. 1987. Power and centrality: A family of measures. Amer. J. Sociol. 92, 1170--1182.
• 3: Brandes, U. 2001. A faster algorithm for betweenness centrality. J. Mathe. Sociol. 25, 163-- 177.
• 4: Deepayan Chakrabarti , Spiros Papadimitriou , Dharmendra S. Modha , Christos Faloutsos, Fully automatic cross-associations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014064]
• 5: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Proceedings of the eighth international conference on World Wide Web, p.1623-1640, May 1999, Toronto, Canada
• 6: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 7: Fiedler, M. 1973. Algebraic connectivity of graphs. Czech. Math. J. 23, 298--305.
• 8: Gary William Flake , Steve Lawrence , C. Lee Giles , Frans M. Coetzee, Self-Organization and Identification of Web Communities, Computer, v.35 n.3, p.66-71, March 2002 [doi>10.1109/2.989932]
• 9: Freeman, L. C. 1977. A set of measures of centrality based upon betweenness. Sociometry 40, 35--41.
• 10: Girvan, M. and Newman, M. E. J. 2002. Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 7821--7826.
• 11: Hotelling, H. 1936. Simplified calculation of principal component. Psychometrika 1, 27--35.
• 12: Imrich, W. and Klavzar, S. 2000. Product Graphs: Structure and Recognition, John Wiley.
• 13: Kernighan, B. W. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. 49, 291--307.
• 14: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 15: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceedings of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
• 16: Jiming Liu , XiaoLong Jin , Kwok Ching Tsui, Autonomy Oriented Computing: From Problem Solving to Complex Systems Modeling (Multiagent Systems, Artificial Societies, and Simulated Organizations), Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 17: Liu, J., Jin, X. L., and Tsui, K. C. 2005. Autonomy oriented computing (AOC): Formulating computational systems with autonomous components. IEEE Trans. Syst., Man, Cybern. Part A: Syst. Humans 35, 879--902.
• 18: Lusseau, D. 2003. The emergent properties of a dolphin social network. In Proceedings of the Royal Society of London B 270, S186--S188.
• 19: Newman, M. E. J. 2001. Scientific collaboration networks II: Shortest paths, weighted networks, and centrality. Phys. Rev. E 64, 016132.
• 20: Newman, M. E. J. 2004a. Detecting community structure in networks. European Phys. J. B 38, 321--330.
• 21: Newman, M. E. J. 2004b. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 69, 066133.
• 22: Newman, M. E. J. and Girvan, M. 2004. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113.
• 23: Peter Pirolli , James Pitkow , Ramana Rao, Silk from a sow's ear: extracting usable structures from the Web, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.118-125, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238450]
• 24: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 25: Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., and Parisi, D. 2004. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences 101, 2658--2663.
• 26: Reichardt, J. and Bornholdt, S. 2004. Detecting fuzzy community structure in complex networks with a Potts model. Phys. Rev. Lett. 93, 218701.
• 27: Scott, J. 2000. Social Network Analysis: A Handbook. Sage Publications, London, UK.
• 28: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 29: Joshua R. Tyler , Dennis M. Wilkinson , Bernardo A. Huberman, Email as spectroscopy: automated discovery of community structure within organizations, Communities and technologies, Kluwer, B.V., Deventer, The Netherlands, 2003
• 30: Wu, F. and Huberman, B. A. 2004. Finding communities in linear time: A physics approach. European Phys. J. B 38, 331--338.
• 31: Bo Yang , William Cheung , Jiming Liu, Community Mining from Signed Social Networks, IEEE Transactions on Knowledge and Data Engineering, v.19 n.10, p.1333-1348, October 2007 [doi>10.1109/TKDE.2007.1061]
• 32: Bo Yang , Jiming Liu, An Autonomy Oriented Computing (AOC) Approach to Distributed Network Community Mining, Proceedings of the First International Conference on Self-Adaptive and Self-Organizing Systems, p.151-160, July 09-11, 2007 [doi>10.1109/SASO.2007.10]
• 33: Zachary, W. W. 1977. An information flow model for conflict and fission in small groups. J. Anthro. Res. 33, 452--473.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Theory

Keywords:
Complex network, World Wide Web, centrality, community mining, graph theory