research-article

Public Access

Motifs in Temporal Networks

Authors:

Ashwin Paranjape,

Austin R. Benson,

Jure LeskovecAuthors Info & Claims

WSDM '17: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining

Pages 601 - 610

https://doi.org/10.1145/3018661.3018731

Published: 02 February 2017 Publication History

Abstract

Networks are a fundamental tool for modeling complex systems in a variety of domains including social and communication networks as well as biology and neuroscience. The counts of small subgraph patterns in networks, called network motifs, are crucial to understanding the structure and function of these systems. However, the role of network motifs for temporal networks, which contain many timestamped links between nodes, is not well understood.

Here we develop a notion of a temporal network motif as an elementary unit of temporal networks and provide a general methodology for counting such motifs. We define temporal network motifs as induced subgraphs on sequences of edges, design several fast algorithms for counting temporal network motifs, and prove their runtime complexity. We also show that our fast algorithms achieve 1.3x to 56.5x speedups compared to a baseline method.

We use our algorithms to count temporal network motifs in a variety of real-world datasets. Results show that networks from different domains have significantly different motif frequencies, whereas networks from the same domain tend to have similar motif frequencies. We also find that measuring motif counts at various time scales reveals different behavior.

References

[1]

M. Araujo, S. Papadimitriou, S. Günnemann, C. Faloutsos, P. Basu, A. Swami, E. E. Papalexakis, and D. Koutra. Com2: fast automatic discovery of temporal ('comet') communities. In PAKDD, 2014.

[2]

A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.

[3]

A. R. Benson, D. F. Gleich, and J. Leskovec. Tensor spectral clustering for partitioning higher-order network structures. In SDM, 2015.

[4]

A. R. Benson, D. F. Gleich, and J. Leskovec. Higher-order organization of complex networks. Science, 353(6295):163--166, 2016.

[5]

M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis. Mining graph evolution rules. In ECML PKDD, 2009.

Digital Library

[6]

D. M. Dunlavy, T. G. Kolda, and E. Acar. Temporal link prediction using matrix and tensor factorizations. TKDD, 5(2):10, 2011.

Digital Library

[7]

S. Gurukar, S. Ranu, and B. Ravindran. Commit: A scalable approach to mining communication motifs from dynamic networks. In SIGMOD, 2015.

Digital Library

[8]

P. Holme and J. Saramäki. Temporal networks. Physics Reports, 519(3):97--125, 2012.

[9]

H. Huang, J. Tang, S. Wu, L. Liu, et al. Mining triadic closure patterns in social networks. In WWW, 2014.

Digital Library

[10]

A. Z. Jacobs, S. F. Way, J. Ugander, and A. Clauset. Assembling thefacebook: Using heterogeneity to understand online social network assembly. In Web Science, 2015.

[11]

D. Kondor, M. Pósfai, I. Csabai, and G. Vattay. Do the rich get richer? an empirical analysis of the bitcoin transaction network. PLOS ONE, 9(2):e86197, 2014.

[12]

G. Kossinets and D. J. Watts. Empirical analysis of an evolving social network. Science, 311(5757):88--90, 2006.

[13]

L. Kovanen, M. Karsai, K. Kaski, J. Kertész, and J. Saramäki. Temporal motifs in time-dependent networks. JSTAT, 2011(11):P11005, 2011.

[14]

M. Latapy. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical Computer Science, 407(1):458--473, 2008.

Digital Library

[15]

J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In CHI, 2010.

Digital Library

[16]

J. Leskovec, D. P. Huttenlocher, and J. M. Kleinberg. Governance in social media: A case study of the wikipedia promotion process. In ICWSM, 2010.

[17]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. TKDD, 1(1):2, 2007.

Digital Library

[18]

R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheffer, and U. Alon. Superfamilies of evolved and designed networks. Science, 303(5663):1538--1542, 2004.

[19]

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824--827, 2002.

[20]

M. E. Newman. The structure and function of complex networks. SIAM Review, 45(2):167--256, 2003.

Digital Library

[21]

P. Panzarasa, T. Opsahl, and K. M. Carley. Patterns and dynamics of users' behavior and interaction: Network analysis of an online community. JASIST, 2009.

[22]

A. Pinar, C. Seshadhri, and V. Vishal. ESCAPE: Efficiently Counting All 5-Vertex Subgraphs. arXiv: 1610.09411, 2016.

[23]

C. Tantipathananandh, T. Berger-Wolf, and D. Kempe. A framework for community identification in dynamic social networks. In KDD, 2007.

Digital Library

[24]

J. Ugander, L. Backstrom, and J. Kleinberg. Subgraph frequencies: Mapping the empirical and extremal geography of large graph collections. In WWW, 2013.

[25]

A. Vazquez, R. Dobrin, D. Sergi, J.-P. Eckmann, Z. Oltvai, and A.-L. Barabási. The topological relationship between the large-scale attributes and local interaction patterns of complex networks. PNAS, 101(52):17940--17945, 2004.

[26]

B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi. On the evolution of user interaction in Facebook. In WOSN, 2009.

Digital Library

[27]

S. Wernicke and F. Rasche. Fanmod: a tool for fast network motif detection. Bioinformatics, 22(9):1152--1153, 2006.

Digital Library

[28]

Y. Wu, C. Zhou, J. Xiao, J. Kurths, and H. J. Schellnhuber. Evidence for a bimodal distribution in human communication. PNAS, 107(44):18803--18808, 2010.

[29]

Ö. N. Yaveroğlu, N. Malod-Dognin, D. Davis, Z. Levnajic, V. Janjic, R. Karapandza, A. Stojmirovic, and N. Pržulj. Revealing the hidden language of complex networks. Scientific Reports, 4, 2014.

[30]

Q. Zhao, Y. Tian, Q. He, N. Oliver, R. Jin, and W.-C. Lee. Communication motifs: a tool to characterize social communications. In CIKM, 2010.

Digital Library

Cited By

Grigoriev AMironov SSidorov S(2024)Dynamics of Friendship Index in Complex NetworksModelling10.3390/modelling50300635:3(1219-1238)Online publication date: 5-Sep-2024
https://doi.org/10.3390/modelling5030063
Yang SZhu WZhang KDiao YBai Y(2024)Influence Maximization in Temporal Social Networks with the Mixed K-Shell MethodElectronics10.3390/electronics1313253313:13(2533)Online publication date: 27-Jun-2024
https://doi.org/10.3390/electronics13132533
Arregui-García BLonga ALotito QMeloni SCencetti G(2024)Patterns in Temporal Networks with Higher-Order Egocentric StructuresEntropy10.3390/e2603025626:3(256)Online publication date: 13-Mar-2024
https://doi.org/10.3390/e26030256
Show More Cited By

Index Terms

Motifs in Temporal Networks
1. Information systems
  1. Information systems applications
    1. Data mining
  2. World Wide Web
    1. Web mining
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

Finding functional promoter motifs by computational methods: a word of caution

The standard practice in the analysis of promoters is to select promoter regions of convenient length. This may lead to false results when searching for Transcription Factor Binding Sites (TFBSs), since the sequences may contain coding segments. In such ...
Counting motifs in probabilistic biological networks
BCB '15: Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics

Studying the distribution of motifs in biological networks provides valuable insights about the key functions of these networks. Finding motifs in networks is however a computationally challenging task. This task is further complicated by the fact that ...
Counting independent motifs in probabilistic networks
BCB '16: Proceedings of the 7th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics

Biological networks provide great potential to understand how cells function. Network motifs, frequent topological patterns, are key structures through which biological networks operate. Counting independent (i.e. non-overlapping) copies of a given ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '17: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining

February 2017

868 pages

ISBN:9781450346757

DOI:10.1145/3018661

General Chairs:
Maarten de Rijke
University of Amsterdam
,
Milad Shokouhi
Microsoft
,
Program Chairs:
Andrew Tomkins
Google
,
Min Zhang
Tsinghua University

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 February 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Institutes of Health
National Science Foundation
Stanford Data Science Initiative
Defense Advanced Research Projects Agency

Conference

WSDM 2017

Sponsor:

WSDM 2017: Tenth ACM International Conference on Web Search and Data Mining

February 6 - 10, 2017

Cambridge, United Kingdom

Acceptance Rates

WSDM '17 Paper Acceptance Rate 80 of 505 submissions, 16%;

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

407
Total Citations
View Citations
5,333
Total Downloads

Downloads (Last 12 months)909
Downloads (Last 6 weeks)112

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Grigoriev AMironov SSidorov S(2024)Dynamics of Friendship Index in Complex NetworksModelling10.3390/modelling50300635:3(1219-1238)Online publication date: 5-Sep-2024
https://doi.org/10.3390/modelling5030063
Yang SZhu WZhang KDiao YBai Y(2024)Influence Maximization in Temporal Social Networks with the Mixed K-Shell MethodElectronics10.3390/electronics1313253313:13(2533)Online publication date: 27-Jun-2024
https://doi.org/10.3390/electronics13132533
Arregui-García BLonga ALotito QMeloni SCencetti G(2024)Patterns in Temporal Networks with Higher-Order Egocentric StructuresEntropy10.3390/e2603025626:3(256)Online publication date: 13-Mar-2024
https://doi.org/10.3390/e26030256
Zhu YGuo JLi HLiu SLi Y(2024)TSAGNN: Temporal link predict method based on two stream adaptive graph neural networkIntelligent Data Analysis10.3233/IDA-23736728:1(77-97)Online publication date: 3-Feb-2024
https://doi.org/10.3233/IDA-237367
Steer BArnold NBa CLambiotte RYousaf HJeub LMurariu FKapoor SRico PChan RChan LAlford JClegg RCuadrado FBarnes MZhong PPougué-Biyong JAlnaimi A(2024)Raphtory: The temporal graph engine for Rust and PythonJournal of Open Source Software10.21105/joss.059409:95(5940)Online publication date: Mar-2024
https://doi.org/10.21105/joss.05940
Guliyev RHaldar AFerhatosmanoglu H(2024)D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural NetworksProceedings of the VLDB Endowment10.14778/3681954.368196117:11(2764-2777)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681961
Bénichou AMasson JVestergaard C(2024)Compression-based inference of network motif setsPLOS Computational Biology10.1371/journal.pcbi.101246020:10(e1012460)Online publication date: 10-Oct-2024
https://doi.org/10.1371/journal.pcbi.1012460
Xiu-Xiu ZXiaoWen XKaiYue ZChuang LZi-Ke Z(2024)A node-embedding-based influence maximization algorithm in temporal networkSCIENTIA SINICA Physica, Mechanica & Astronomica10.1360/SSPMA-2023-013454:3(230511)Online publication date: 6-Feb-2024
https://doi.org/10.1360/SSPMA-2023-0134
Li JQi JHuang YCao LYu YDong JSerra ESpezzano F(2024)MoTTo: Scalable Motif Counting with Time-aware Topology Constraint for Large-scale Temporal GraphsProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679694(1195-1204)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679694
Chen XXiong YZhang SZhang JZhang YZhou SWu XZhang MLiu TWang WSerra ESpezzano F(2024)DTFormer: A Transformer-Based Method for Discrete-Time Dynamic Graph Representation LearningProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679568(301-311)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679568
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents