Top

Social Network Analysis and Mining

Published in:

01-12-2018 | Original Article

Stream graphs and link streams for the modeling of interactions over time

Authors: Matthieu Latapy, Tiphaine Viard, Clémence Magnien

Published in: Social Network Analysis and Mining | Issue 1/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Graph theory provides a language for studying the structure of relations, and it is often used to study interactions over time too. However, it poorly captures the intrinsically temporal and structural nature of interactions, which calls for a dedicated formalism. In this paper, we generalize graph concepts to cope with both aspects in a consistent way. We start with elementary concepts like density, clusters, or paths, and derive from them more advanced concepts like cliques, degrees, clustering coefficients, or connected components. We obtain a language to directly deal with interactions over time, similar to the language provided by graphs to deal with relations. This formalism is self-consistent: usual relations between different concepts are preserved. It is also consistent with graph theory: graph concepts are special cases of the ones we introduce. This makes it easy to generalize higher level objects such as quotient graphs, line graphs, k-cores, and centralities. This paper also considers discrete versus continuous time assumptions, instantaneous links, and extensions to more complex cases.

previous article A data reduction approach using hypergraphs to visualize communities and brokers in social networks

next article Remote assessment of countries’ cyber weapon capabilities

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Unless explicitly specified, we always consider simple and undirected graphs and stream graphs; we discuss more general cases in Sect. 20.

A partition of a set X into k parts is a family \((P_1, P_2, \ldots , P_k)\) of k subsets of X, such that \(\cup _i P_i = X\) and \(P_i \cap P_j = \emptyset\) for all \(i\ne j\).

This is a generalization to stream graphs of the \(\Delta\)-density introduced in Viard and Latapy (2014) for link streams.

Barabási A-L, Pósfai M (2016) Network science. Cambridge University Press, Cambridge

Barrat A, Cattuto C (2013) Temporal networks of face-to-face human interactions. Springer, Berlin, Heidelberg, pp 191–216

Batagelj V, Praprotnik S (2016) An algebraic approach to temporal network analysis based on temporal quantities. Social Netw Anal Mining 6(1):28:1–28:22MATH

Berge C (1962) The theory of graphs and its applications. Wiley, New YorkMATH

Bhadra S, Ferreira A (2012) Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs. J Internet Serv Appl 3(3):269–275CrossRef

Blondel VD, Decuyper A, Krings G (2015) A survey of results on mobile phone datasets analysis. EPJ Data Sci 4(1):10CrossRef

Blonder B, Wey TW, Dornhaus A, James R, Sih A (2012) Temporal dynamics and network analysis. Methods Ecol Evol 3(6):958–972CrossRef

Bondy JA (1976) Graph Theory Appl. Elsevier Science Ltd., Oxford

Bui-Xuan B-M, Ferreira A, Jarry A (2003) Computing shortest, fastest, and foremost journeys in dynamic networks. Int J Found Comput Sci 14(2):267–285MathSciNetMATHCrossRef

Butts CT (2008) A relational event framework for social action. Sociol Methodol 38(1):155–200CrossRef

Caceres RS, Berger-Wolf T (2013) Temporal scale of dynamic networks. Springer, Berlin, Heidelberg, pp 65–94CrossRef

Casteigts A, Flocchini P, Mans B, Santoro N (2015) Shortest, fastest, and foremost broadcast in dynamic networks. Int J Found Comput Sci 26(4):499–522MathSciNetMATHCrossRef

Casteigts A, Flocchini P, Quattrociocchi W, Santoro N (2012) Time-varying graphs and dynamic networks. IJPEDS 27(5):387–408

Chinelate CE, Borges VA, Klaus W, Artur Z, da Silva APC (2015) Time centrality in dynamic complex networks. Adv Complex Syst 18(7–8):1550023MathSciNet

Conan V, Leguay J, Friedman T (2007) Characterizing pairwise inter-contact patterns in delay tolerant networks. In: Proceedings of the 1st international conference on autonomic computing and communication systems, autonomics ’07, pages 19:1–19:9, ICST, Brussels, Belgium, Belgium. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering)

Corneli M, Latouche P, Rossi F (2016) Block modelling in dynamic networks with non-homogeneous poisson processes and exact icl. Social Netw Anal Mining 6(1):55CrossRef

Corneli M, Latouche P, Rossi F (2015) Modelling time evolving interactions in networks through a non stationary extension of stochastic block models. In: ASONAM '15 Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015, pp 1590–1591

David E, Jon K (2010) Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, New YorkMATH

Diestel R (2012) Graph theory, 4th edn, volume 173 of Graduate texts in mathematics. Springer, New York

Doreian P, Stokman F (1997) Evolution of social networks. The journal of mathematical sociology, vol 1. Gordon and Breach Publishers, AmsterdamMATH

Dutta BL, Ezanno P, Vergu E (2014) Characteristics of the spatio-temporal network of cattle movements in France over a 5-year period. Prev Vet Med 117(1):79–94CrossRef

Flores J, Romance M (2017) On eigenvector-like centralities for temporal networks: discrete vs. continuous time scales. J Comput Appl Math 330:1041–1051MathSciNetMATHCrossRef

Gaumont N, Magnien C, Latapy M (2016a) Finding remarkably dense sequences of contacts in link streams. Social Netw Anal Mining 6(1):87:1–87:14

Gaumont N, Viard T, Fournier-S’niehotta R, Wang Q, Latapy M (2016b) Analysis of the temporal and structural features of threads in a mailing-list. Springer International Publishing, Cham, pp 107–118

Gauvin L, Panisson A, Cattuto C (2014) Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach. PLOS One 9(1):1–13CrossRef

George B, Kim S (2013) Spatio-temporal Networks: modeling and algorithms. SpringerBriefs in Computer Science. Springer, New YorkMATHCrossRef

Gomes LH, Almeida VAF, Almeida JM, Castro FDO, Bettencourt LA (2009) Quantifying social and opportunistic behavior in email networks. Adv Complex Syst 12(01):99–112CrossRef

Gulyás L, Kampis G, Legendi RO (2013) Elementary models of dynamic networks. Eur Phys J Spec Top 222(6):1311–1333CrossRef

Hamon R, Borgnat P, Flandrin P, Robardet C (2015) Duality between temporal networks and signals: Extraction of the temporal network structures. CoRR. https://arxiv.org/abs/1505.03044

Harshaw CR, Bridges RA, Iannacone MD, Reed JW, Goodall JR (2016) Graphprints: towards a graph analytic method for network anomaly detection. In: Proceedings of the 11th annual cyber and information security research conference, CISRC ’16, ACM, New York, NY, USA, pp 15:1–15:4

Hernández-Orallo E, Cano JC, Calafate CT, Manzoni P (2016) New approaches for characterizing inter-contact times in opportunistic networks. Ad Hoc Netw 52:160–172 (Modeling and Performance Evaluation of Wireless Ad Hoc Networks) CrossRef

Holme P (2015) Modern temporal network theory: a colloquium. Eur Phys J B 88(9):234CrossRef

Holme P, Saramäki J (2012) Temporal networks. Phys Rep 519(3):97–125 (Temporal Networks) CrossRef

Huanhuan W, Cheng J, Huang S, Ke Y, Yi L, Yanyan X (2014) Path problems in temporal graphs. Proc VLDB Endow 7(9):721–732CrossRef

Hulovatyy Y, Chen H, Milenkovic T (2016) Exploring the structure and function of temporal networks with dynamic graphlets. Bioinformatics 32(15):2402CrossRef

Karsai M, Kivelä M, Pan RK, Kaski K, Kertész J, Barabási A-L, Saramäki J (2011) Small but slow world: How network topology and burstiness slow down spreading. Phys Rev E 83:025102CrossRef

Kivelä M, Arenas A, Barthelemy M, Gleeson JP, Moreno Y, Porter MA (2014) Multilayer networks. J Complex Netw 2(3):203–271CrossRef

Kivelä M, Cambe J, Saramäki J, Karsai M (2018) Mapping temporal-network percolation to weighted, static event graphs. Sci Rep 8:12357. https://doi.org/10.1038/s41598-018-29577-2 CrossRef

Kostakos V (2009) Temporal graphs. Physica A Stat Mech Appl 388(6):1007–1023MathSciNetCrossRef

Kovanen L, Karsai M, Kaski K, Kertész J, Saramäki J (2011) Temporal motifs in time-dependent networks. J Stat Mech Theory Exp 2011(11):P11005CrossRef

Kovanen L, Kaski K, Kertész J, Saramäki J (2013) Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences. PNAS 110(45):18070–18075. https://doi.org/10.1073/pnas.1307941110 CrossRef

Krings G, Karsai M, Bernhardsson S, Blondel VD, Saramäki J (2012) Effects of time window size and placement on the structure of an aggregated communication network. EPJ Data Sci 1(1):4CrossRef

Latapy M, Magnien C, Del Vecchio N (2008) Basic notions for the analysis of large two-mode networks. Soc Netw 30(1):31–48CrossRef

Laurent G, Saramäki J, Karsai M (2015) From calls to communities: a model for time-varying social networks. Eur Phys J B 88(11):301MathSciNetCrossRef

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

Leskovec J, Backstrom L, Kumar R, Tomkins A (2008) Microscopic evolution of social networks. In: Ying L, Bing L, Sunita S (eds) Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, ACM, Las Vegas, Nevada, USA, Aug 24–27, pp 462–470

Léo Y, Crespelle C, Fleury E (2015) Non-altering time scales for aggregation of dynamic networks into series of graphs. In Felipe Huici and Giuseppe Bianchi, editors, Proceedings of the 11th ACM conference on emerging networking experiments and technologies, CoNEXT 2015, ACM, Heidelberg, Germany, Dec 1–4, 2015, pp 29:1–29:7

Magnien C, Tarissan F (2015) Time evolution of the importance of nodes in dynamic networks. In: ASONAM '15 Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015. ACM, New York, pp 1200–1207

Martinet L, Crespelle C, Fleury E (2014) Dynamic contact network analysis in hospital wards. Springer International Publishing, Cham, pp 241–249

Masuda N, Lambiotte R (2016) A guide to temporal networks. Series on complexity science, vol 4. World Scientific, UKMATHCrossRef

Matias C, Miele V (2017) Statistical clustering of temporal networks through a dynamic stochastic block model. J R Stat Soc Ser B 79:1119–1141MathSciNetMATHCrossRef

Michail O (2015) An introduction to temporal graphs: an algorithmic perspective. Springer International Publishing, Cham, pp 308–343MATH

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

Newman M (2010) Networks: an introduction. Oxford University Press Inc, New YorkMATHCrossRef

Nicosia V, Tang J, Musolesi M, Russo G, Mascolo C, Latora V (2012) Components in time-varying graphs. Chaos: an Interdisciplinary. J Nonlinear Sci 22(2):023101MATH

Nicosia V, Tang J, Mascolo C, Musolesi M, Russo G, Latora V (2013) Graph metrics for temporal networks. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 15–40

Paranjape A, Benson AR, Leskovec J (2017) Motifs in temporal networks. In: de Rijke M, Shokouhi M, Tomkins A, Zhang M (eds) Proceedings of the Tenth ACM international conference on web search and data mining, WSDM 2017, Cambridge, United Kingdom, February 6–10, pp 601–610

Payen A, Tabourier L, Latapy M (2017) Impact of temporal features of cattle exchanges on the size and speed of epidemic outbreaks. In: Osvaldo G, Beniamino M, Sanjay M, Giuseppe B, Carmelo Maria T, Ana Maria ACR, David T, Bernady OA, Elena NS, Alfredo C (eds) Computational science and its applications—ICCSA 2017—17th International Conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part II, volume 10405 of Lecture Notes in Computer Science. Springer, New York, pp 84–97

Pei J, Silvestri F, Tang J (eds) (2015) Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015, ACM. Paris, France, August 25–28, 2015

Perry PO, Wolfe PJ (2013) Point process modelling for directed interaction networks. J R Stat Soc Ser B (Statistical Methodology) 75(5):821–849MathSciNetMATHCrossRef

Praprotnik S, Batagelj V (2016) Semirings for temporal network analysis. CoRR https://arxiv.org/abs/1603.08261

Ribeiro B, Perra N, Baronchelli A (2013) Quantifying the effect of temporal resolution on time-varying networks. Sci Rep 3:3006CrossRef

Rocha LEC, Masuda N (2014) Random walk centrality for temporal networks. N J Phys 16(6):063023MathSciNetCrossRef

Rozenshtein P, Tatti N, Gionis A (2017) Finding dynamic dense subgraphs. ACM Trans Knowl Discov Data 11(3):271–2730CrossRef

Santoro N, Quattrociocchi W, Flocchini P, Casteigts A, Amblard F (2011) Time-varying graphs and social network analysis: Temporal indicators and metrics. In: 3rd AISB social networks and multiagent systems symposium (SNAMAS), pp 32–38

Saramäki J, Holme P (2015) Exploring temporal networks with greedy walks. Eur Phys J B 88(12):334CrossRef

Scholtes I, Wider N, Garas A (2016) Higher-order aggregate networks in the analysis of temporal networks: path structures and centralities. Eur Phys J B 89(3):61CrossRef

Scott J (2017) Social network analysis. SAGE Publications, Thousand Oaks

Sikdar S, Ganguly N, Mukherjee A (2015) Time series analysis of temporal networks. CoRR https://arxiv.org/abs/1512.01344

Sizemore AE, Bassett DS (2018) Dynamic graph metrics: tutorial, toolbox, and tale. NeuroImage 180:417–427CrossRef

Snijders TAB (2001) The statistical evaluation of social network dynamics. Sociol Methodol 31(1):361–395CrossRef

Snijders TAB, van de Bunt GG, Steglich. CEG (2010) Introduction to stochastic actor-based models for network dynamics. Soc Netw 32(1):44–60 (Dynamics of Social Networks) CrossRef

Stadtfeld C, Block P (2017) Interactions, actors, and time: dynamic network actor models for relational events. Sociol Sci 4:318–352CrossRef

Stadtfeld C, Hollway J, Block P (2017) Dynamic network actor models: investigating coordination ties through time. Sociol Methodol 47(1):1–40CrossRef

Starnini M, Baronchelli A, Barrat A, Pastor-Satorras R (2012) Random walks on temporal networks. Phys Rev E 85:056115CrossRef

Sun J, Tao D, Faloutsos C (2006) Beyond streams and graphs: dynamic tensor analysis. In: Tina ER, Lyle HU, Mark C, Dimitrios G (eds) Proceedings of the Twelfth ACM SIGKDD international conference on knowledge discovery and data mining, ACM, Philadelphia, PA, USA, Aug 20–23, 2006, pp 374–383

Takaguchi T, Yano Y, Yoshida Y (2016) Coverage centralities for temporal networks. Eur Phys J B 89(2):35CrossRef

Tang J, Musolesi M, Mascolo C, Latora V (2010) Characterising temporal distance and reachability in mobile and online social networks. SIGCOMM Comput Commun Rev 40(1):118–124CrossRef

Tang J, Scellato S, Musolesi M, Mascolo C, Latora V (2010) Small-world behavior in time-varying graphs. Phys Rev E 81:055101CrossRef

Tang J, Musolesi M, Mascolo C, Latora V, Nicosia V (2010) Analysing information flows and key mediators through temporal centrality metrics. In: Proceedings of the 3rd workshop on social network systems, SNS ’10, ACM. New York, NY, USA, pp 3:1–3:6

Taylor D, Myers SA, Clauset A, Porter MA, Mucha PJ (2017) Eigenvector-based centrality measures for temporal networks. Multiscale Model Simul 15(1):537–574MathSciNetMATHCrossRef

Thompson WH, Brantefors P, Fransson P (2017) From static to temporal network theory: applications to functional brain connectivity. Netw Neurosci 1(2):69–99CrossRef

Tiphaine V, Raphaël FS (2018) Movie rating prediction using content-based and link stream features. CoRR, abs/1805.02893

Uddin S, Hossain L, Wigand RT (2014) New direction in degree centrality measure: towards a time-variant approach. Int J Inform Technol Decis Making 13(4):865CrossRef

Uddin S, Khan A, Piraveenan M (2016) A set of measures to quantify the dynamicity of longitudinal social networks. Complexity 21(6):309–320MathSciNetCrossRef

Uddin MS, Mahendra P, Chung KSK, Hossain L (2013) Topological analysis of longitudinal networks. In: 46th Hawaii International Conference on System Sciences, HICSS 2013, Wailea, HI, USA, 7–10 January, 2013. pp 3931–3940

Viard T, Latapy M, Magnien C (2016) Computing maximal cliques in link streams. Theor Comput Sci 609:245–252MathSciNetMATHCrossRef

Viard T, Fournier-S’niehotta R, Magnien C, Latapy M (2018) Discovering patterns of interest in IP traffic using cliques in bipartite link streams. In: Cornelius S, Coronges K, Gonçalves B, Sinatra R, Vespignani A (eds) Complex networks IX. CompleNet 2018. Springer proceedings in complexity. Springer, Cham

Viard T, Latapy M (2014) Identifying roles in an IP network with temporal and structural density. In: 2014 Proceedings IEEE INFOCOM Workshops, IEEE, Toronto, ON, Canada, April 27–May 2, 2014, pp 801–806

Viard T, Latapy M, Magnien Cl (2015) Revealing contact patterns among high-school students using maximal cliques in link streams. In: ASONAM '15 Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015. ACM, New York, pp 1517–1522CrossRef

Wasserman S, Faust K (1994) Social network analysis: Methods and applications, vol 8. Cambridge University Press, CambridgeMATHCrossRef

Wehmuth K, Fleury É, Ziviani A (2016) Multiaspect graphs: algebraic representation and algorithms. Algorithms 10(4):1MathSciNetMATHCrossRef

Wehmuth K, Fleury É, Ziviani A (2016) On multiaspect graphs. Theor Comput Sci 651:50–61MathSciNetMATHCrossRef

Wehmuth K, Ziviani A, Fleury E (2015) A unifying model for representing time-varying graphs. In: 2015 IEEE international conference on data science and advanced analytics, DSAA 2015, Campus des Cordeliers, IEEE, Paris, France, October 19–21, 2015, pp 1–10

West DB (2000) Introduction to graph theory, 2nd edn. Prentice Hall, Prentice

Whitbeck J, de Amorim MD, Conan V, Guillaume JL (2012) Temporal reachability graphs. In: Özgür BA, Eylem E, Lili Q, Alex CS (eds) The 18th annual international conference on mobile computing and networking, Mobicom’12, ACM, Istanbul, Turkey, Aug 22–26, 2012, pp 377–388

Wilmet A, Viard T, Latapy M, Lamarche-PR (2018) Degree-based outliers detection within ip traffic modelled as a link stream. In: Proceedings of the 2nd network traffic measurement and analysis conference (TMA)

Xu KS, Hero AO (2013) Dynamic stochastic blockmodels: statistical models for time-evolving networks. Springer, Berlin, Heidelberg, pp 201–210

Zhao K, Karsai M, Bianconi G (2013) Models, entropy and information of temporal social networks. Springer, Berlin, Heidelberg, pp 95–117CrossRef

Zignani M, Gaito S, Rossi GP, Zhao X, Zheng H, Zhao BY (2014) Link and triadic closure delay: temporal metrics for social network dynamics. In Eytan A, Paul R, Munmun De C, Bernie H, Alice HH (eds) Proceedings of the eighth international conference on weblogs and social media, ICWSM 2014, The AAAI Press, Ann Arbor, Michigan, USA, June 1–4, 2014

Title: Stream graphs and link streams for the modeling of interactions over time
Authors: Matthieu Latapy
Tiphaine Viard
Clémence Magnien
Publication date: 01-12-2018
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2018
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-018-0537-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2018

Remote assessment of countries’ cyber weapon capabilities

Understanding expert finding systems: domains and techniques

Incorporating pre-training in long short-term memory networks for tweet classification

Attribute selection for improving spam classification in online social networks: a rough set theory-based approach

Emotion detection from text and speech: a survey

Generalized relationships between characteristic path length, efficiency, clustering coefficients, and density

Premium Partner