publication . Conference object . 2015

Revealing contact patterns among high-school students using maximal cliques in link streams

Viard , Tiphaine; Latapy , Matthieu; Magnien , Clémence;
Open Access English
  • Published: 25 Aug 2015
  • Publisher: HAL CCSD
  • Country: France
Abstract
International audience; Interaction traces between humans are usually rich in information concerning the patterns and habits of individuals. Such datasets have been recently made available, and more and more researchers address the new questions raised by this data. A link stream is a sequence of triplets (t, u, v) indicating that an interaction occurred between u and v at time t, and as such is a natural representation of these data. We generalize the classical notion of cliques in graphs to such link streams: for a given ∆, a ∆-clique is a set of nodes and a time interval such that all pairs of nodes in this set interact at least every ∆ during this time inter...
Subjects
free text keywords: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], [ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [ INFO.INFO-SI ] Computer Science [cs]/Social and Information Networks [cs.SI]
19 references, page 1 of 2

[1] David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65:21-46, 1996.

[2] Coen Bron and J Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9), 1973. [OpenAIRE]

[3] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. CoRR, abs/1012.0009, 2010.

[4] Ciro Cattuto, Wouter Van den Broeck, Alain Barrat, Vittoria Colizza, Jean-Franc¸ois Pinton, and Alessandro Vespignani. Dynamics of personto-person interactions from distributed rfid sensor networks. PLoS ONE, 5(7):e11596, 07 2010.

[5] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal of Computing, 14(1):210-223, 1985. [OpenAIRE]

[6] David Eppstein and Darren Strash. Listing all maximal cliques in large sparse real-world graphs. Experimental Algorithms, pages 364-375, 2011.

[7] Julie Fournet and Alain Barrat. Contact patterns among high school students. PLoS ONE, 9:e107878, 2014.

[8] Petter Holme and Jari Sarama¨ki. Temporal networks. Physics Reports, 519:97-125, 2012.

[9] Theus Hossmann, Thrasyvoulos Spyropoulos, and Franck Legendre. A complex network analysis of human mobility. In NETSCICOM 2011, 3rd IEEE International Workshop on Network Science for Communication Networks, in conjuction with IEEE INFOCOM 2011, April 15, 2011, Shanghai, China, Shanghai, CHINE, 04 2011. [OpenAIRE]

[10] Theus Hossmann, Thrasyvoulos Spyropoulos, and Franck Legendre. Putting contacts into context: Mobility modeling beyond inter-contact times. In Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '11, pages 18:1-18:11, New York, NY, USA, 2011. ACM. [OpenAIRE]

[11] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119-123, 3 1988.

[12] Anna-Kaisa Pietila¨nen and Christophe Diot. Dissemination in opportunistic social networks: The role of temporal communities. In Proceedings of the Thirteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '12, pages 165-174, New York, NY, USA, 2012. ACM.

[13] Michele Starnini, Andrea Baronchelli, and Romualdo Pastor-Satorras. Modeling human dynamics of face-to-face interaction networks. Phys. Rev. Lett., 110:168701, Apr 2013. [OpenAIRE]

[14] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363:28-42, 2006. [OpenAIRE]

[15] Tiphaine Viard. Source code in python for drawing link streams: https://github.com/TiphaineV/LinkStreamViz, 2014.

19 references, page 1 of 2
Abstract
International audience; Interaction traces between humans are usually rich in information concerning the patterns and habits of individuals. Such datasets have been recently made available, and more and more researchers address the new questions raised by this data. A link stream is a sequence of triplets (t, u, v) indicating that an interaction occurred between u and v at time t, and as such is a natural representation of these data. We generalize the classical notion of cliques in graphs to such link streams: for a given ∆, a ∆-clique is a set of nodes and a time interval such that all pairs of nodes in this set interact at least every ∆ during this time inter...
Subjects
free text keywords: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], [ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [ INFO.INFO-SI ] Computer Science [cs]/Social and Information Networks [cs.SI]
19 references, page 1 of 2

[1] David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65:21-46, 1996.

[2] Coen Bron and J Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9), 1973. [OpenAIRE]

[3] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. CoRR, abs/1012.0009, 2010.

[4] Ciro Cattuto, Wouter Van den Broeck, Alain Barrat, Vittoria Colizza, Jean-Franc¸ois Pinton, and Alessandro Vespignani. Dynamics of personto-person interactions from distributed rfid sensor networks. PLoS ONE, 5(7):e11596, 07 2010.

[5] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal of Computing, 14(1):210-223, 1985. [OpenAIRE]

[6] David Eppstein and Darren Strash. Listing all maximal cliques in large sparse real-world graphs. Experimental Algorithms, pages 364-375, 2011.

[7] Julie Fournet and Alain Barrat. Contact patterns among high school students. PLoS ONE, 9:e107878, 2014.

[8] Petter Holme and Jari Sarama¨ki. Temporal networks. Physics Reports, 519:97-125, 2012.

[9] Theus Hossmann, Thrasyvoulos Spyropoulos, and Franck Legendre. A complex network analysis of human mobility. In NETSCICOM 2011, 3rd IEEE International Workshop on Network Science for Communication Networks, in conjuction with IEEE INFOCOM 2011, April 15, 2011, Shanghai, China, Shanghai, CHINE, 04 2011. [OpenAIRE]

[10] Theus Hossmann, Thrasyvoulos Spyropoulos, and Franck Legendre. Putting contacts into context: Mobility modeling beyond inter-contact times. In Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '11, pages 18:1-18:11, New York, NY, USA, 2011. ACM. [OpenAIRE]

[11] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119-123, 3 1988.

[12] Anna-Kaisa Pietila¨nen and Christophe Diot. Dissemination in opportunistic social networks: The role of temporal communities. In Proceedings of the Thirteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '12, pages 165-174, New York, NY, USA, 2012. ACM.

[13] Michele Starnini, Andrea Baronchelli, and Romualdo Pastor-Satorras. Modeling human dynamics of face-to-face interaction networks. Phys. Rev. Lett., 110:168701, Apr 2013. [OpenAIRE]

[14] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363:28-42, 2006. [OpenAIRE]

[15] Tiphaine Viard. Source code in python for drawing link streams: https://github.com/TiphaineV/LinkStreamViz, 2014.

19 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue