Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation

• Achlioptas D, McSherry F (2001) Fast computation of low rank matrix approximation. In: Proceedings of 33rd STOC. ACM Press, New York

• Alon N, Matias Y, Szegedy M (1996) The space complexity of approximating the frequency moments. In: STOC ’96: proceedings of the twenty-eighth annual ACM symposium on theory of computing, New York, NY, USA. ACM, New York, pp 20–29

• Alon N, Yuster R, Zwick U (1997) Finding and counting given length cycles. Algorithmica 17(3):209–223

  Google Scholar 

• Alon N, Gibbons PB, Matias Y, Szegedy M (2002) Tracking join and self-join sizes in limited storage, pp 10–20

• Bar-Yosseff Z, Kumar R, Sivakumar D (2002) Reductions in streaming algorithms, with an application to counting triangles in graphs. In: SODA ’02: proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, pp 623–632

• Becchetti L, Boldi P, Castillo C, Gionis A (2008) Efficient semi-streaming algorithms for local triangle counting in massive graphs. In: Proceedings of ACM KDD, Las Vegas, NV, USA

• Buriol LS, Frahling G, Leonardi S, Marchetti-Spaccamela A, Sohler C (2006) Counting triangles in data streams. In: PODS ’06: proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, New York, NY, USA. ACM, pp 253–262

• Chung F, Lu L, Vu V (2003) Eigenvalues of random power law graphs. Ann Comb 7(1):21–33

  MATH  MathSciNet  Google Scholar 

• Coppersmith D, Winograd S (1987) Matrix multiplication via arithmetic progressions. In: STOC ’87: proceedings of the nineteenth annual ACM conference on theory of computing, New York, NY, USA. ACM, pp 1–6

• Deerwester S, Dumais ST, Furnas GW, Landauer TK, Harshman R (1990) Indexing by latent semantic analysis. J Am Soc Inf Sci 41:391–407

  Article  Google Scholar 

• Demmel J (1997) Applied numerical linear algebra. SIAM, Philadelphia

  MATH  Google Scholar 

• Drineas P, Kannan R (2003) Pass efficient algorithms for approximating large matrices. In: SODA ’03: proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics, pp 223–232

• Eckmann J-P, Moses E (2002) Curvature of co-links uncovers hidden thematic layers in the world wide web. PNAS 99(9):5825–5829

  Article  MathSciNet  Google Scholar 

• Faloutsos M, Faloutsos P, Faloutsos C (1999) On power-law relationships of the internet topology. In: SIGCOMM, pp 251–262

• Farkas IJ, Derenyi I, Barabasi A-L, Vicsek T (2001) Spectra of “real-world” graphs: beyond the semi-circle law. Phys Rev E 64:1

  Article  Google Scholar 

• Frieze A, Kannan R, Vempala S (1998) Fast Monte-Carlo algorithms for finding low-rank approximations. In: Proceedings of the 39th annual IEEE symposium on foundations of computer science, pp 370–378

• Gilbert AC, Kotidis Y, Muthukrishnan S, Strauss MJ (2003) One-pass wavelet decompositions of data streams. IEEE TKDE 15:2003

  Google Scholar 

• Golub G, Van Loan C (1989) Matrix computations, 2nd edn. Johns Hopkins Press, Baltimore

• Latapy M (2008) Main-memory triangle computations for very large (sparse (power-law)) graphs. Theor Comput Sci 407(1–3):458–473

  Article  MATH  MathSciNet  Google Scholar 

• Liben-Nowell D (2005) An algorithmic approach to social networks. PhD thesis, Massachusetts Institute of Technology, Electrical Engineering and Computer Science Department, June 2005

• Mihail M, Papadimitriou C (2002) On the eigenvalue power law. In: Lecture notes on computer sciences, vol 2483. Springer, Berlin

• Newman MEJ (2001) Clustering and preferential attachment in growing networks. Phys Rev E 64:016131

  Google Scholar 

• Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45:167–256

  Article  MATH  MathSciNet  Google Scholar 

• Schank T, Wagner D (2004) DELIS-TR-0043—finding, counting and listing all triangles in large graphs, an experimental study. Techreport 0043

• Tsourakakis C (2008) Fast counting of triangles in large real networks, without counting: algorithms and laws. In: ICDM

• Tsourakakis CE, Kang U, Miller GL, Faloutsos C (2009a) Doulion: counting triangles in massive graphs with a coin. In: Elder JF, Fogelman-Souli F, Flach PA, Zaki M (eds) Proceedings of KDD. ACM, pp 837–846

• Tsourakakis CE, Kolountzakis MN, Miller GL (2009b) Approximate triangle counting. CoRR, abs/0904.3761

• Turk M, Pentland A (1991) Eigenfaces for recognition. J Cogn Neurosci 3(1):71–86

  Article  Google Scholar 

• Wasserman S, Faust K (1994) Social network analysis. Cambridge University Press, Cambridge

  Google Scholar 

Download references