nach oben

Data Mining and Knowledge Discovery

Erschienen in:

01.09.2016

An efficient exact algorithm for triangle listing in large graphs

verfasst von: Sofiane Lagraa, Hamida Seba

Erschienen in: Data Mining and Knowledge Discovery | Ausgabe 5/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents a new efficient exact algorithm for listing triangles in a large graph. While the problem of listing triangles in a graph has been considered before, dealing with large graphs continues to be a challenge. Although previous research has attempted to tackle the challenge, this is the first contribution that addresses this problem on a compressed copy of the input graph. In fact, the proposed solution lists the triangles without decompressing the graph. This yields interesting improvements in both storage requirement of the graphs and their time processing.

Vorheriger Artikel ClusPath: a temporal-driven clustering to infer typical evolution paths

Nächster Artikel Exact and efficient top-K inference for multi-target prediction by querying separable linear relational models

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

i.e., we make no difference between (u, v) and (v, u) in \(V\times V\). We also assume that G is simple \(((v,v)\notin E\) for all v, and that there is no multiple edge).

The k-core of a graph is the largest node induced subgraph with a minimum degree of at least k.

http://ferrolab.dmi.unict.it/ri/ri.html#description.

Batagelj V, Zaversnik MZ (2011) Fast algorithms for determining (generalized) core groups in social networks. Adv Data Anal Classif 5(2):129–145MathSciNetCrossRefMATH

Becchetti L, Boldi P, Castillo C, Gionis A (2010) Efficient algorithms for large-scale local triangle counting. ACM Trans Knowl Discov Data 4(3):13:1–13:28. doi:10.1145/1839490.1839494 CrossRef

Björklund A, Pagh R, Williams V, Zwick U (2014) Listing triangles. In: Esparza J, Fraigniaud P, Husfeldt T, Koutsoupias E (eds) Automata, languages, and programming. Lecture notes in computer science. Springer, Berlin, pp 223–234. doi:10.1007/978-3-662-43948-7_19

Boldi P, Vigna S (2004) The webgraph framework i: Compression techniques. In: Proceedings of the 13th international conference on world wide web, WWW ’04, pp 595–602. ACM, New York doi:10.1145/988672.988752

Bonnici V, Giugno R, Pulvirenti A, Shasha D, Ferro A (2013) A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinform 14:S13CrossRef

Capelle C, Habib M, de Montgolfier F (2002) Graph decompositions and factorizing permutations. Discret Math Theor Comput Sci 5(1):55–70MathSciNetMATH

Chen C, Lin CX, Fredrikson M, Christodorescu M, Yan X, Han J (2009) Mining graph patterns efficiently via randomized summaries. Proc VLDB Endow 2(1):742–753. doi:10.14778/1687627.1687711 CrossRef

Chiba N, Nishizeki T (1985) Arboricity and subgraph listing algorithms. SIAM J Comput 14(1):210–223. doi:10.1137/0214017 MathSciNetCrossRefMATH

Chu S, Cheng J (2012) Triangle listing in massive networks. ACM Trans Knowl Discov Data 6(4):17:1–17:32. doi:10.1145/2382577.2382581 CrossRef

Cowan D, James I, Stanton R (1972) Graph decomposition for undirected graphs. In: 3rd S-E conference on combinatorics, graph theory and computing, pp 281–290

Dahlhaus E, Gustedt J, McConnell RM (2001) Efficient and practical algorithms for sequential modular decomposition. J Algorithms 41(2):360–387. doi:10.1006/jagm.2001.1185. http://www.sciencedirect.com/science/article/pii/S019667740191185X

Dementiev R (2006) Algorithm engineering for large data sets hardware, software, algorithms. Ph.D. thesis, Saarland University, Saarbrucken

de Montgolfier F (2003) Modular decomposition of graphs: theory, extensions and algorithms. Ph.D. thesis, Université des Sciences et Techniques du Languedoc, Montpellier

Fan W, Li J, Wang X, Wu Y (2012) Query preserving graph compression. In: Proceedings of the 2012 ACM SIGMOD international conference on management of data, SIGMOD ’12, pp 157–168. ACM, New York. doi:10.1145/2213836.2213855

Gallai T (1967) Transitiv orientierbare graphen. Acta Math Hung 18:25–66MathSciNetCrossRefMATH

Habib M, de Montgolfier F, Paul C (2004) A simple linear-time modular decomposition algorithm for graphs, using order extension. In: Proceedings of the algorithm theory—SWAT 2004, 9th Scandinavian workshop on algorithm theory, Humlebaek, Denmark, 8–10 July 2004, pp 187–198

Habib M, Paul C (2010) A survey of the algorithmic aspects of modular decomposition. Comput Sci Rev 4(1):41–59CrossRefMATH

Habib M, Paul C, Viennot L (1999) Partition refinement techniques: an interesting algorithmic tool kit. Int J Found Comput Sci 10(2):147–170MathSciNetCrossRefMATH

Hu X, Tao Y, Chung CW (2013) Massive graph triangulation. In: Proceedings of the 2013 ACM SIGMOD international conference on management of data, SIGMOD ’13, pp 325–336. ACM, New York. doi:10.1145/2463676.2463704

Itai A, Rodeh M (1978) Finding a minimum circuit in a graph. SIAM J Comput 7(4):413–423MathSciNetCrossRefMATH

Kolountzakis MN, Miller G, Peng R, Tsourakakis CE (2010) Efficient triangle counting in large graphs via degree-based vertex partitioning. In: Kumar R, Sivakumar D (eds) Algorithms and models for the web-graph. Lecture notes in computer science. Springer, Berlin, pp 15–24. doi:10.1007/978-3-642-18009-5_3

Lagraa S, Seba H, Khennoufa R, M’Baya A, Kheddouci H (2014) A distance measure for large graphs based on prime graphs. Pattern Recognit 47(9):2993–3005CrossRefMATH

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

Leskovec J, Krevl A (2014) SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data

Mcconnell RM, Spinrad JP (2000) Ordered vertex partitioning. Discret Math Theor Comput Sci 4(1). http://dmtcs.episciences.org/274

Möhring R (1985) Algorithmic aspect of the substitution decomposition in optimization over relation, set system and boolean function. Ann Oper Res 4:195–225MathSciNetCrossRef

Möhring R, Radermacher F (1984) Substitution decomposition and connection with combinatorial optimization. Ann Discret Math 19:257–356MATH

Ortmann M, Brandes U (2014) Triangle listing algorithms: Back from the diversion. In: 2014 proceedings of the sixteenth workshop on algorithm engineering and experiments, ALENEX 2014, Portland, Oregon, USA, 5 Jan 2014, pp 1–8

Schank T (2007) Algorithmic aspects of triangle-based network analysis. Ph.D. thesis, Universität Karlsruhe, Karlsruhe

Schank T, Wagner D (2005) Finding, counting and listing all triangles in large graphs, an experimental study. In: Proceedings of the 4th International conference on experimental and efficient algorithms, WEA’05, pp 606–609. Springer-Verlag, Berlin, Heidelberg. doi:10.1007/11427186_54

Szklarczyk D, Franceschini A, Kuhn M, Simonovic M, Roth A, Minguez P, Doerks T, Stark M, Muller J, Bork P, Jensen L, Mering CV (2011) The string database in 2011: functional interaction networks of proteins, globally integrated and scored. Nucleic Acids Res 39:D561–D568CrossRef

Tedder M, Corneil D, Habib M, Paul C (2008) Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto L, Damgrd I, Goldberg L, Halldrsson M, Inglfsdttir A, Walukiewicz I (eds) Automata, languages and programming. Lecture notes in computer science. Springer, Berlin, pp 634–645. doi:10.1007/978-3-540-70575-8_52

Tsourakakis CE, Kang U, Miller GL, Faloutsos C (2009) Doulion: counting triangles in massive graphs with a coin. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’09, pp 837–846. ACM, New York. doi:10.1145/1557019.1557111

Titel: An efficient exact algorithm for triangle listing in large graphs
verfasst von: Sofiane Lagraa
Hamida Seba
Publikationsdatum: 01.09.2016
Verlag: Springer US
Erschienen in: Data Mining and Knowledge Discovery / Ausgabe 5/2016
Print ISSN: 1384-5810
Elektronische ISSN: 1573-756X
DOI: https://doi.org/10.1007/s10618-016-0451-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 5/2016

Scalable time series classification

Irrevocable-choice algorithms for sampling from a stream

Ensembles of label noise filters: a ranking approach

Exact and efficient top-K inference for multi-target prediction by querying separable linear relational models

Bayesian Wishart matrix factorization

Optimizing network robustness by edge rewiring: a general framework

Premium Partner