SCAN: a structural clustering algorithm for networks

ABSTRACT

Network clustering (or graph partitioning) is an important task for the discovery of underlying structures in networks. Many algorithms find clusters by maximizing the number of intra-cluster edges. While such algorithms find useful and interesting structures, they tend to fail to identify and isolate two kinds of vertices that play special roles - vertices that bridge clusters (hubs) and vertices that are marginally connected to clusters (outliers). Identifying hubs is useful for applications such as viral marketing and epidemiology since hubs are responsible for spreading ideas or disease. In contrast, outliers have little or no influence, and may be isolated as noise in the data. In this paper, we proposed a novel algorithm called SCAN (Structural Clustering Algorithm for Networks), which detects clusters, hubs and outliers in networks. It clusters vertices based on a structural similarity measure. The algorithm is fast and efficient, visiting each vertex only once. An empirical evaluation of the method using both synthetic and real datasets demonstrates superior performance over other methods such as the modularity-based algorithms.

REFERENCES

• 1: S. Wasserman and K. Faust, "Social Network Analysis." Cambridge University Press, Cambridge (1994).
• 2: R. Albert, H. Jeong, and A.-L. Barabási, "Diameter of the world-wide web." Nature 401, 130--131 (1999).
• 3: J. M. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, "The Web as a graph: Measurements, models and methods." In Proceedings of the International Conference on Combinatorics and Computing, number 1627 in Lecture Notes in Computer Science, pp. 1--18, Springer, Berlin (1999).
• 4: Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha , Ming Gu , Horst D. Simon, A Min-max Cut Algorithm for Graph Partitioning and Data Clustering, Proceedings of the 2001 IEEE International Conference on Data Mining, p.107-114, November 29-December 02, 2001
• 5: 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]
• 6: R. Guimera and L. A. N. Amaral, "Functional cartography of complex metabolic networks." Nature 433, 895--900 (2005).
• 7: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 8: 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]
• 9: Y. Wang, D. Chakrabarti, C. Wang and C. Faloutsos, "Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint", SRDS 2003 (pages 25--34), Florence, Italy
• 10: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise". In Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD'96), Portland, OR, pages 291--316. AAAI Press, 1996.
• 11: M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks", Phys. Rev. E 69, 026113 (2004).
• 12: A. Clauset, M. E. J. Newman, and C. Moore, "Finding community in very large networks", Physical Review E 70, 066111 (2004).
• 13: D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks," Nature, 393:440--442 (1998)
• 14: W. M. Rand, "Objective criteria for the evaluation of clustering methods." Journal of the American Statistical Association, 66, pp 846--850 (1971).
• 15: L. Hubert and P. Arabie, "Comparing Partitions". Journal of Classification, 193--218, 1985.
• 16: G. W. Milligan and M. C. Cooper, "A study of the comparability of external criteria for hierarchical cluster analysis", Multivariate BehavioralResearch, 21, 441--458, 1986.
• 17: http://cs.unm.edu/~aaron/research/fastmodularity.htm.
• 18: http://www.orgnet.com/.
• 19: http://www-personal.umich.edu/~mejn/netdata/.
• 20: P. Erdös and A. Rényi, Publ. Math. (Debrecen) 6, 290 (1959).
• 21: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 22: A.-L. Barabási and Z. N. Oltvai, Nature Reviews Genetics 5, 101--113 (2004).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Performance

Keywords:
community Structure, graph partitioning, hubs, network clustering, outliers