Mining scale-free networks using geodesic clustering

ABSTRACT

Many real-world graphs have been shown to be scale-free---vertex degrees follow power law distributions, vertices tend to cluster, and the average length of all shortest paths is small. We present a new model for understanding scale-free networks based on multilevel geodesic approximation, using a new data structure called a multilevel mesh.Using this multilevel framework, we propose a new kind of graph clustering for data reduction of very large graph systems such as social, biological, or electronic networks. Finally, we apply our algorithms to real-world social networks and protein interaction graphs to show that they can reveal knowledge embedded in underlying graph structures. We also demonstrate how our data structures can be used to quickly answer approximate distance and shortest path queries on scale-free networks.

REFERENCES

• 1: A. L. Barabasi, R. Albert, H. Jeong, and G. Bianconi. Power-law distribution of the world wide web. Science, 287, 2000.
• 2: B. Bollobas. Random Graphs. Cambridge University Press, second edition, 2001.
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 4: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 5: Z. Drezner and H. W. Hamacher. Facility Location: Applications and Theory. Springer, 2002.
• 6: M. Garland. Multiresolution modeling: Survey & future opportunities. In State of the Art Report, pages 111--131. Eurographics, Sept. 1999.
• 7: L. Holder, D. Cook, and S. Djoko. Substructure discovery in the subdue system. In Proceedings of the Workshop on Knowledge Discovery in Databases, pages 169--180, 1994.
• 8: H. Jeong, S. P. Mason, A. L. Barabasi, and Z. Oltvai. Lethality and centrality in protein networks. In Nature, volume 411, pages 41--42, 2001.
• 9: 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]
• 10: V. Krebs. Mapping networks of terrorist cells. Connections, 24, 2001.
• 11: B. Mirkin. Mathematical Classification and Clustering. Kluwer Academic Publishers, 1996.
• 12: M. E. J. Newman. The structure and function of complex networks. In SIAM Review, volume 45, pages 167--256, 2003.
• 13: M. E. J. Newman. Detecting community structure in networks. In Eur. Phys. J. B., 2004.
• 14: J. O'Madadhain, D. Fisher, S. White, and Y. Boey. The JUNG (Java Universal Network/Graph) framework. Technical report, UC Irvine, 2003.
• 15: Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775057]
• 16: Kirk Schloegel , George Karypis , Vipin Kumar, Graph partitioning for high-performance scientific simulations, Sourcebook of parallel computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 17: Takashi Washio , Hiroshi Motoda, State of the art of graph-based data mining, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959249]
• 18: S. Wasserman and K. Faust. Social network analysis. Cambridge University Press, Cambridge, 1994.
• 19: Scott White , Padhraic Smyth, Algorithms for estimating relative importance in networks, 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.956782]
• 20: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 21: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
clustering, graphs, scale-free networks, social networks