Mining scale-free networks using geodesic clustering

Andrew Y. Wu, Michael Garland, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationKDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
PublisherAssociation for Computing Machinery
Pages719-724
Number of pages6
ISBN (Print)1581138881, 9781581138887
DOIs
StatePublished - 2004
EventKDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - Seattle, WA, United States
Duration: Aug 22 2004Aug 25 2004

Publication series

NameKDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

OtherKDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Country/TerritoryUnited States
CitySeattle, WA
Period8/22/048/25/04

Keywords

  • Clustering
  • Graphs
  • Scale-free networks
  • Social networks

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Mining scale-free networks using geodesic clustering'. Together they form a unique fingerprint.

Cite this