Efficient semi-streaming algorithms for local triangle counting in massive graphs

ABSTRACT

In this paper we study the problem of local triangle counting in large graphs. Namely, given a large graph G = (V;E) we want to estimate as accurately as possible the number of triangles incident to every node υ ∈ V in the graph. The problem of computing the global number of triangles in a graph has been considered before, but to our knowledge this is the first paper that addresses the problem of local triangle counting with a focus on the efficiency issues arising in massive graphs. The distribution of the local number of triangles and the related local clustering coefficient can be used in many interesting applications. For example, we show that the measures we compute can help to detect the presence of spamming activity in large-scale Web graphs, as well as to provide useful features to assess content quality in social networks.

For computing the local number of triangles we propose two approximation algorithms, which are based on the idea of min-wise independent permutations (Broder et al. 1998). Our algorithms operate in a semi-streaming fashion, using O(jV j) space in main memory and performing O(log jV j) sequential scans over the edges of the graph. The first algorithm we describe in this paper also uses O(jEj) space in external memory during computation, while the second algorithm uses only main memory. We present the theoretical analysis as well as experimental results in massive graphs demonstrating the practical efficiency of our approach.

REFERENCES

• 1: N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209--223, 1997.
• 2: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 3: V. Batagelj and A. Mrvar. A subquadratic triad census algorithm for large sparse networks with small maximum degree. Social Networks, 23:237--243, 2001.
• 4: T. Bohman, C. Cooper, and A. M. Frieze. Min-wise independent linear permutations. Electr. J. Comb, 7, 2000.
• 5: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 6: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 7: Andrei Z. Broder, Identifying and Filtering Near-Duplicate Documents, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.1-10, June 21-23, 2000
• 8: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 9: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 10: Luciana S. Buriol , Gereon Frahling , Stefano Leonardi , Alberto Marchetti-Spaccamela , Christian Sohler, Counting triangles in data streams, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142388]
• 11: Carlos Castillo , Debora Donato , Luca Becchetti , Paolo Boldi , Stefano Leonardi , Massimo Santini , Sebastiano Vigna, A reference collection for web spam, ACM SIGIR Forum, v.40 n.2, p.11-24, December 2006 [doi>10.1145/1189702.1189703]
• 12: Carlos Castillo , Debora Donato , Aristides Gionis , Vanessa Murdock , Fabrizio Silvestri, Know your neighbors: web spam detection using the web topology, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277814]
• 13: Don Coppersmith , Ravi Kumar, An improved data stream algorithm for frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 14: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 15: Camil Demetrescu , Irene Finocchi , Andrea Ribichini, Trading off space for passes in graph streaming problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.714-723, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109635]
• 16: J.-P. Eckmann and E. Moses. Curvature of co-links uncovers hidden thematic layers in the world wide web. PNAS, 99(9):5825--5829, 2002.
• 17: J. Feigenbaum, S. Kannan, M. A. Gregor, S. Suri, and J. Zhang. On graph problems in a semi-streaming model. In ICALP, 2004.
• 18: Dennis Fetterly , Mark Manasse , Marc Najork, Spam, damn spam, and statistics: using statistical analysis to locate spam web pages, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017077]
• 19: Dániel Fogaras , Balázs Rácz, Scaling link-based similarity search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060839]
• 20: David Gibson , Ravi Kumar , Andrew Tomkins, Discovering large dense subgraphs in massive graphs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 21: A. Gulli , A. Signorini, The indexable web is more than 11.5 billion pages, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062789]
• 22: T. Haveliwala. Efficient computation of pagerank. Technical report, Stanford University, 1999.
• 23: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 24: Piotr Indyk, A small approximately min-wise independent family of hash functions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.454-456, January 17-19, 1999, Baltimore, Maryland, United States
• 25: A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM Journal of Computing, 7(4):413--423, 1978.
• 26: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, 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.775126]
• 27: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1481-1493, May 17, 1999
• 28: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 29: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167--256, 2003.
• 30: T. Schank and D. Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Proceedings of the 4th International Workshop on Experimental and Efficient Algorithms (WEA), 2005.
• 31: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 32: H. T. Welser, E. Gleave, D. Fisher, and M. Smith. Visualizing the signatures of social roles in online discussion groups. The Journal of Social Structure, 8(2), 2007.

INDEX TERMS

Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering; Information filtering

General Terms:
Algorithms, Measurement

Keywords:
graph mining, probabilistic algorithms, semi-streaming