nach oben

Social Network Analysis and Mining

Erschienen in:

01.12.2016 | Original Article

Finding remarkably dense sequences of contacts in link streams

verfasst von: Noé Gaumont, Clémence Magnien, Matthieu Latapy

Erschienen in: Social Network Analysis and Mining | Ausgabe 1/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A link stream is a set of quadruplets (b, e, u, v) meaning that a link exists between u and v from time b to time e. Link streams model many real-world situations like contacts between individuals, connections between devices, and others. Much work is currently devoted to the generalization of classical graph and network concepts to link streams. We argue that the density is a valuable notion for understanding and characterizing links streams. We propose a method to capture specific groups of links that are structurally and temporally densely connected and show that they are meaningful for the description of link streams. To find such groups, we use classical graph community detection algorithms, and we assess obtained groups. We apply our method to several real-world contact traces (captured by sensors) and demonstrate the relevance of the obtained structures.

Vorheriger Artikel A mathematical model of news propagation on online social network and a control strategy for rumor spreading

Nächster Artikel Network completion by leveraging similarity of nodes

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 "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

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

Nur mit Berechtigung zugänglich

Other community detection methods can be applied.

http://www.sociopatterns.org.

Candidates with one link represent 83 % of all candidates.

https://bitbucket.org/nGaumont/densityanalysis/.

Ahn Y-Y, Bagrow JP, Lehmann S (2010) Link communities reveal multiscale complexity in networks. Nature 466(7307):761–764CrossRef

Aynaud, T, Fleury E, Guillaume J-L, Wang Q (2013) Communities in evolving networks: definitions, detection, and analysis techniques. In: Mukherjee A, Choudhury M, Peruani F, Ganguly N, Mitra B (eds) Dynamics on and of Complex Networks, vol 2. Springer, New York pp 159–200

Balalau OD, Bonchi F, Chan T-HH, Gullo F, Sozio M (2015) Finding Subgraphs with maximum total density and limited overlap. In: Proceedings of the eighth ACM international conference on web search and data mining—WSDM ’15. ACM Press, New York, pp 379–388

Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech: Theory Exp 2008(10):P10008CrossRef

Bogdanov P, Mongiovì M, Singh AK (2011) Mining heavy subgraphs in time-evolving networks. In: 2011 IEEE 11th international conference on data mining. IEEE, pp 81–90

Casteigts A, Flocchini P, Quattrociocchi W, Santoro N (2011) Time-varying graphs and dynamic networks. In: Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), vol 6811. LNCS, pp 346–359

Cazabet R, Amblard F, Hanachi C (2010) Detection of overlapping communities in dynamical social networks. In: 2010 IEEE second international conference on social computing (SocialCom)

Crofoot MC, Kays RW, Wikelski M (2015) Data from: Shared decision-making drives collective movement in wild baboons. Movebank Data Repository. doi:10.5441/001/1.kn0816jn

Eagle N, Pentland AS, Lazer D (2009) Inferring social network structure using mobile phone data. PNAS 106(usually 1):15274–15278CrossRef

Epasto A, Lattanzi S, Sozio M (may 2015) Efficient densest subgraph computation in evolving graphs. In: Proceedings of the 24th international conference on world wide web. International World Wide Web Conferences Steering Committee, pp 300–310

Falkowski T, Barth A, Spiliopoulou M (2007) DENGRAPH: a density-based community detection algorithm. In: Proceedings of the IEEE/WIC/ACM international conference on web intelligence, WI 2007. IEEE, pp 112–115

Falkowski T, Spiliopoulou M, Bartelheimer J (2006) Community dynamics mining. In: Proceedings of 14th European conference on information systems (ECIS 2006). Citeseer

Fournet J, Barrat A (2014) Contact patterns among high school students. PloS One 9(9):e107878CrossRef

Gaumont N, Viard T, Fournier-S’niehotta R, Wang Q, Latapy M (2016) Analysis of the temporal and structural features of threads in a mailing-list. In: Cherifi H, Gonçalves B, Menezes R, Sinatra R (eds) Complex networks VII. Springer, Switzerland, pp 107–118

Greene D, Doyle D, Cunningham P (2010) Tracking the evolution of communities in dynamic social networks. In: 2010 International conference on advances in social networks analysis and mining (ASONAM), ASONAM ’10. IEEE Computer Society, Washington, pp 176–183

Hartmann T, Kappes A, Wagner D (2014) Clustering evolving networks. arXiv preprint arXiv:1401.3516

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

Holme P, Saramäki J (eds) (2013) Temporal networks. Understanding complex systems. Springer, Berlin

Mitra B, Tabourier L, Roth C (2012) Intrinsically dynamic network communities. Comput Netw 56(3):1041–1053CrossRef

Rozenshtein P, Tatti N, Gionis A (2014) Discovering dynamic communities in interaction networks. In: Calders T, Esposito F, Hüllermeier E, Meo R (eds) Machine learning and knowledge discovery in databases, vol 8725., Lecture notes in computer scienceSpringer, Berlin, pp 678–693

Samudrala R, Moult J (1998) A graph-theoretic algorithm for comparative modeling of protein structure. J Mol Biol 279(1):287–302CrossRef

Saramäki J, Moro E (2015) From seconds to months: an overview of multi-scale dynamics of mobile telephone calls. Eur Phys J B 88(6):164CrossRef

Sekara V, Stopczynski A, Lehmann S (2016) Fundamental structures of dynamic social networks. In: Proceedings of the national academy of sciences, p 201602803

Speidel L, Takaguchi T, Masuda N (2015) Community detection in directed acyclic graphs. Eur Phys J B 88(8):203CrossRef

Strandburg-Peshkin A, Farine DR, Couzin ID, Crofoot MC (2015) Shared decision-making drives collective movement in wild baboons. Science 348(6241):1358–1361CrossRef

Tournoux P-U, Leguay J, Benbadis F, Conan V, Dias de Amorim M, Whitbeck J (2009) The accordion phenomenon: analysis, characterization, and impact on DTN routing. In: IEEE INFOCOM 2009—the 28th conference on computer communications. IEEE, pp 1116–1124

Viard T, Latapy M (apr 2014) Identifying roles in an IP network with temporal and structural density. In: 2014 IEEE Conference on computer communications workshops (INFOCOM WKSHPS). IEEE, pp 801–806

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

Yang J, Leskovec J (feb 2013) Overlapping community detection at scale. In: Proceedings of the sixth ACM international conference on Web search and data mining—WSDM ’13. ACM Press, New York, p 587

Titel: Finding remarkably dense sequences of contacts in link streams
verfasst von: Noé Gaumont
Clémence Magnien
Matthieu Latapy
Publikationsdatum: 01.12.2016
Verlag: Springer Vienna
Erschienen in: Social Network Analysis and Mining / Ausgabe 1/2016
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-016-0396-z

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

On the prevalence of hierarchies in social networks

Effects of missing data in multilayer networks

Comparison of sentiment lexicon development techniques for event prediction

Computing competing cascades on signed networks

Unsupervised graph-based pattern extraction for multilingual emotion classification

An empirical comparison of Big Graph frameworks in the context of network analysis