Butterfly counting in bipartite networks

Seyed Vahid Sanei-Mehri; Ahmet Erdem Sariyüce; Srikanta Tirthapura

doi:10.1145/3219819.3220097

Butterfly counting in bipartite networks

Seyed Vahid Sanei-Mehri
, Ahmet Erdem Sariyüce
, Srikanta Tirthapura

Department of Computer Science and Engineering

University at Buffalo

Iowa State University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

104 Scopus citations

Abstract

We consider the problem of counting motifs in bipartite affiliation networks, such as author-paper, user-product, and actor-movie relations. We focus on counting the number of occurrences of a “butterfly”, a complete 2 × 2 biclique, the simplest cohesive higher-order structure in a bipartite graph. Our main contribution is a suite of randomized algorithms that can quickly approximate the number of butterflies in a graph with a provable guarantee on accuracy. An experimental evaluation on large real-world networks shows that our algorithms return accurate estimates within a few seconds, even for networks with trillions of butterflies and hundreds of millions of edges.

Original language	English
Title of host publication	KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher	Association for Computing Machinery
Pages	2150-2159
Number of pages	10
ISBN (Print)	9781450355520
DOIs	https://doi.org/10.1145/3219819.3220097
State	Published - Jul 19 2018
Event	24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018 - London, United Kingdom Duration: Aug 19 2018 → Aug 23 2018

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference	24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018
Country/Territory	United Kingdom
City	London
Period	08/19/18 → 08/23/18

Access to Document

10.1145/3219819.3220097

Cite this

Sanei-Mehri, S. V., Sariyüce, A. E., & Tirthapura, S. (2018). Butterfly counting in bipartite networks. In KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 2150-2159). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Association for Computing Machinery. https://doi.org/10.1145/3219819.3220097

Sanei-Mehri, Seyed Vahid ; Sariyüce, Ahmet Erdem ; Tirthapura, Srikanta. / Butterfly counting in bipartite networks. KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2018. pp. 2150-2159 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{d2c7407746954c7c9942c8ff1a083b7d,

title = "Butterfly counting in bipartite networks",

abstract = "We consider the problem of counting motifs in bipartite affiliation networks, such as author-paper, user-product, and actor-movie relations. We focus on counting the number of occurrences of a “butterfly”, a complete 2 × 2 biclique, the simplest cohesive higher-order structure in a bipartite graph. Our main contribution is a suite of randomized algorithms that can quickly approximate the number of butterflies in a graph with a provable guarantee on accuracy. An experimental evaluation on large real-world networks shows that our algorithms return accurate estimates within a few seconds, even for networks with trillions of butterflies and hundreds of millions of edges.",

author = "Sanei-Mehri, \{Seyed Vahid\} and Sariy{\"u}ce, \{Ahmet Erdem\} and Srikanta Tirthapura",

note = "Publisher Copyright: {\textcopyright} 2018 Association for Computing Machinery.; 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018 ; Conference date: 19-08-2018 Through 23-08-2018",

year = "2018",

month = jul,

day = "19",

doi = "10.1145/3219819.3220097",

language = "English",

isbn = "9781450355520",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "2150--2159",

booktitle = "KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

address = "United States",

}

Sanei-Mehri, SV, Sariyüce, AE & Tirthapura, S 2018, Butterfly counting in bipartite networks. in KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery, pp. 2150-2159, 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018, London, United Kingdom, 08/19/18. https://doi.org/10.1145/3219819.3220097

Butterfly counting in bipartite networks. / Sanei-Mehri, Seyed Vahid; Sariyüce, Ahmet Erdem; Tirthapura, Srikanta.
KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2018. p. 2150-2159 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Butterfly counting in bipartite networks

AU - Sanei-Mehri, Seyed Vahid

AU - Sariyüce, Ahmet Erdem

AU - Tirthapura, Srikanta

PY - 2018/7/19

Y1 - 2018/7/19

N2 - We consider the problem of counting motifs in bipartite affiliation networks, such as author-paper, user-product, and actor-movie relations. We focus on counting the number of occurrences of a “butterfly”, a complete 2 × 2 biclique, the simplest cohesive higher-order structure in a bipartite graph. Our main contribution is a suite of randomized algorithms that can quickly approximate the number of butterflies in a graph with a provable guarantee on accuracy. An experimental evaluation on large real-world networks shows that our algorithms return accurate estimates within a few seconds, even for networks with trillions of butterflies and hundreds of millions of edges.

AB - We consider the problem of counting motifs in bipartite affiliation networks, such as author-paper, user-product, and actor-movie relations. We focus on counting the number of occurrences of a “butterfly”, a complete 2 × 2 biclique, the simplest cohesive higher-order structure in a bipartite graph. Our main contribution is a suite of randomized algorithms that can quickly approximate the number of butterflies in a graph with a provable guarantee on accuracy. An experimental evaluation on large real-world networks shows that our algorithms return accurate estimates within a few seconds, even for networks with trillions of butterflies and hundreds of millions of edges.

UR - https://www.scopus.com/pages/publications/85051546174

U2 - 10.1145/3219819.3220097

DO - 10.1145/3219819.3220097

M3 - Conference contribution

SN - 9781450355520

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 2150

EP - 2159

BT - KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

PB - Association for Computing Machinery

T2 - 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018

Y2 - 19 August 2018 through 23 August 2018

ER -

Sanei-Mehri SV, Sariyüce AE, Tirthapura S. Butterfly counting in bipartite networks. In KDD 2018 - Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery. 2018. p. 2150-2159. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/3219819.3220097

Butterfly counting in bipartite networks

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this