Faster maximal clique enumeration in large real-world link streams. (English) Zbl 07923829
Summary: Link streams offer a good model for representing interactions over time. They consist of links \((b, e, u, v)\), where \(u\) and \(v\) are vertices interacting during the whole time interval \([b, e]\). In this paper, we deal with the problem of enumerating maximal cliques in link streams. A clique is a pair \((C,[t_0, t_1])\), where \(C\) is a set of vertices that all interact pairwise during the full interval \([t_0, t_1]\). It is maximal when neither its set of vertices nor its time interval can be increased. Some main works solving this problem are based on the famous Bron-Kerbosch algorithm for enumerating maximal cliques in graphs. We take this idea as a starting point to propose a new algorithm which matches the cliques of the instantaneous graphs formed by links existing at a given time \(t\) to the maximal cliques of the link stream. We prove its correctness and compute its complexity, which is better than the state-of-the art ones in many cases of interest. We also study the output-sensitive complexity, which is close to the output size, thereby showing that our algorithm is efficient. To confirm this, we perform experiments on link streams used in the state of the art, and on massive link streams, up to 100 million links. In all cases our algorithm is faster, mostly by a factor of at least 10 and up to a factor of \(10^4\). Moreover, it scales to massive link streams for which the existing algorithms are not able to provide the solution.
Keywords:
link stream; temporal graph; dynamic network; maximal clique enumeration; Bron-Kerbosch; output-sensitive complexityReferences:
| [1] | P. Bajardi, C. Poletto, J. J. Ramasco, M. Tizzoni, V. Colizza, and A. Vespignani. Human mobility networks, travel restrictions, and the global spread of 2009 h1n1 pandemic. PloS one, 6(1):e16591, 2011. doi:10.1371/journal.pone.0016591. · doi:10.1371/journal.pone.0016591 |
| [2] | S. Banerjee and B. Pal. An efficient updation approach for enumerating maximal (δ, γ)-cliques of a temporal network. Journal of Complex Networks, 10(5):cnac027, 2022. doi: 10.1093/comnet/cnac027. · Zbl 1506.68063 · doi:10.1093/comnet/cnac027 |
| [3] | A. Baudin, M. Danisch, S. Kirgizov, C. Magnien, and M. Ghanem. Clique percolation method: memory efficient almost exact communities. In International Conference on Advanced Data Mining and Applications, pages 113-127. Springer, 2022. doi:10.1007/978-3-030-95408-6_ · doi:10.1007/978-3-030-95408-6_9 |
| [4] | A. Baudin, L. Tabourier, and C. Magnien. Lscpm: Communities in massive real-world link streams by clique percolation method. In 30th International Symposium on Temporal Rep-resentation and Reasoning (TIME 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.TIME.2023.3. · doi:10.4230/LIPIcs.TIME.2023.3 |
| [5] | M. Bentert, A.-S. Himmel, H. Molter, M. Morik, R. Niedermeier, and R. Saitenmacher. Listing all maximal k-plexes in temporal graphs. Journal of Experimental Algorithmics (JEA), 24:1-27, 2019. doi:10.1145/3325859. · doi:10.1145/3325859 |
| [6] | S. Boudebza, R. Cazabet, F. Azouaou, and O. Nouali. Olcpm: An online framework for detecting overlapping communities in dynamic social networks. Computer Communications, 123:36-51, 2018. doi:10.1016/j.comcom.2018.04.003. · doi:10.1016/j.comcom.2018.04.003 |
| [7] | C. Bron and J. Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Com-munications of the ACM, 16(9):575-577, 1973. doi:10.1145/362342.362367. · Zbl 0261.68018 · doi:10.1145/362342.362367 |
| [8] | G. Buehrer and K. Chellapilla. A scalable pattern mining approach to web graph compression with communities. In Proceedings of the 2008 international conference on web search and data mining, pages 95-106, 2008. doi:10.1145/1341531.1341547. · doi:10.1145/1341531.1341547 |
| [9] | A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. doi:10.1007/978-3-642-22450-8_27. · doi:10.1007/978-3-642-22450-8_27 |
| [10] | A. Conte and E. Tomita. On the overall and delay complexity of the cliques and bron-kerbosch algorithms. Theoretical Computer Science, 899:1-24, 2022. doi:10.1016/j.tcs. 2021.11.005. · Zbl 1515.68233 · doi:10.1016/j.tcs.2021.11.005 |
| [11] | A. Das, M. Svendsen, and S. Tirthapura. Incremental maintenance of maximal cliques in a dy-namic graph. The VLDB Journal, 28(3):351-375, 2019. doi:10.1007/s00778-019-00540-5. · doi:10.1007/s00778-019-00540-5 |
| [12] | D. Eppstein, M. Löffler, and D. Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In International Symposium on Algorithms and Computation, pages 403-414. · Zbl 1311.05187 |
| [13] | Springer, 2010. doi:10.1007/978-3-642-17517-6_36. · Zbl 1311.05187 · doi:10.1007/978-3-642-17517-6_36 |
| [14] | J. Fournet and A. Barrat. Contact patterns among high school students. PloS one, 9(9):e107878, 2014. Data available at: http://www.sociopatterns.org/datasets/ high-school-dynamic-contact-networks. doi:10.1371/journal.pone.0107878. · doi:10.1371/journal.pone.0107878 |
| [15] | E. Fratkin, B. T. Naughton, D. L. Brutlag, and S. Batzoglou. Motifcut: regulatory motifs finding with maximum density subgraphs. Bioinformatics, 22(14):e150-e157, 2006. doi: 10.1093/bioinformatics/btl243. · doi:10.1093/bioinformatics/btl243 |
| [16] | V. Gemmetto, A. Barrat, and C. Cattuto. Mitigation of infectious disease at school: targeted class closure vs school closure. BMC infectious diseases, 14(1):1-10, 2014. Data available at: http://www.sociopatterns.org/datasets/ primary-school-temporal-network-data. doi:10.1186/s12879-014-0695-9. · doi:10.1186/s12879-014-0695-9 |
| [17] | D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense subgraphs in massive graphs. In Proceedings of the 31st international conference on Very large data bases, pages 721-732, 2005. |
| [18] | A.-S. Himmel, H. Molter, R. Niedermeier, and M. Sorge. Adapting the bron-kerbosch al-gorithm for enumerating maximal cliques in temporal graphs. Social Network Analysis and Mining, 7(1):1-16, 2017. doi:10.1007/s13278-017-0455-0. · doi:10.1007/s13278-017-0455-0 |
| [19] | P. Holme and J. Saramäki. Temporal networks. Physics reports, 519(3):97-125, 2012. doi: 10.1016/j.physrep.2012.03.001. · doi:10.1016/j.physrep.2012.03.001 |
| [20] | T. Hossmann, F. Legendre, and T. Spyropoulos. From contacts to graphs: Pitfalls in using complex network analysis for dtn routing. In IEEE INFOCOM Workshops 2009, pages 1-6. IEEE, 2009. doi:10.1109/INFCOMW.2009.5072147. · doi:10.1109/INFCOMW.2009.5072147 |
| [21] | L. Isella, J. Stehlé, A. Barrat, C. Cattuto, J. Pinton, and W. Van den Broeck. What’s in a crowd? analysis of face-to-face behavioral networks. Journal of The-oretical Biology, 271(1):166-180, 2011. Data hypertext: http://www.sociopatterns. org/datasets/hypertext-2009-dynamic-contact-network. Data infectious: http://www. sociopatterns.org/datasets/infectious-sociopatterns/. doi:10.1016/j.jtbi.2010. 11.033. · Zbl 1405.92255 · doi:10.1016/j.jtbi.2010.11.033 |
| [22] | D. M. Jacoby and R. Freeman. Emerging network-based tools in movement ecology. Trends in Ecology & Evolution, 31(4):301-314, 2016. doi:10.1016/j.tree.2016.01.011. · doi:10.1016/j.tree.2016.01.011 |
| [23] | I. Koch. Enumerating all connected maximal common subgraphs in two graphs. Theoretical Computer Science, 250(1-2):1-30, 2001. doi:10.1016/S0304-3975(00)00286-3. · Zbl 0952.68105 · doi:10.1016/S0304-3975(00)00286-3 |
| [24] | J. Kunegis. KONECT -The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion, pages 1343-1350, 2013. Data available at: http://konect.cc/networks. |
| [25] | M. Latapy, T. Viard, and C. Magnien. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining, 8(1):1-29, 2018. doi:10.1007/ s13278-018-0537-7. · doi:10.1007/s13278-018-0537-7 |
| [26] | Y. Léo, C. Crespelle, and E. Fleury. Non-altering time scales for aggregation of dynamic networks into series of graphs. Computer Networks, 148:108-119, 2019. doi:10.1016/j. comnet.2018.11.006. · doi:10.1016/j.comnet.2018.11.006 |
| [27] | J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD interna-tional conference on Knowledge discovery in data mining, pages 177-187, 2005. Data available at: https://snap.stanford.edu/data/as-733.html. doi:10.1145/1081870.1081893. · doi:10.1145/1081870.1081893 |
| [28] | J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http: //snap.stanford.edu/data, June 2014. |
| [29] | A. Li, S. P. Cornelius, Y.-Y. Liu, L. Wang, and A.-L. Barabási. The fundamental advantages of temporal networks. Science, 358(6366):1042-1046, 2017. doi:10.1126/science.aai7488. · doi:10.1126/science.aai7488 |
| [30] | R. Mastrandrea, J. Fournet, and A. Barrat. Contact patterns in a high school: a com-parison between data collected using wearable sensors, contact diaries and friendship sur-veys. PloS one, 10(9):e0136497, 2015. Data available at: https://journals.plos.org/ plosone/article?id=10.1371 · doi:10.1371/journal.pone.0136497 |
| [31] | D. Miorandi and F. De Pellegrini. K-shell decomposition for dynamic complex networks. In 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, pages 488-496. IEEE, 2010. |
| [32] | A. Mislove. Online Social Networks: Measurement, Analysis, and Applications to Distributed Information Systems. PhD thesis, Rice University, Department of Computer Science, May 2009. Data available at: https://socialnetworks.mpi-sws.org/data-wosn2008.html. doi:10.1145/1298306.1298311. · doi:10.1145/1298306.1298311 |
| [33] | A. Mislove, H. S. Koppula, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Growth of the flickr social network. In Proceedings of the first workshop on Online social networks, pages 25-30, 2008. Data available at: http://konect.cc/networks/flickr-growth. doi: 10.1145/1397735.1397742. · doi:10.1145/1397735.1397742 |
| [34] | H. Molter, R. Niedermeier, and M. Renken. Isolation concepts applied to temporal clique enumeration. Network Science, 9(S1):S83-S105, 2021. doi:10.1017/nws.2020.38. · doi:10.1017/nws.2020.38 |
| [35] | J. W. Moon and L. Moser. On cliques in graphs. Israel journal of Mathematics, 3(1):23-28, 1965. doi:10.1007/BF02760024. · Zbl 0144.23205 · doi:10.1007/BF02760024 |
| [36] | G. Palla, I. Derényi, I. Farkas, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814-818, 2005. doi:10.1038/ nature03607. · doi:10.1038/nature03607 |
| [37] | P. Panzarasa, T. Opsahl, and K. M. Carley. Patterns and dynamics of users’ behavior and interaction: Network analysis of an online community. Journal of the American Society for Information Science and Technology, 60(5):911-932, 2009. Data available at: http://snap. stanford.edu/data/CollegeMsg.html. doi:10.1002/asi.21015. · doi:10.1002/asi.21015 |
| [38] | A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. In Pro-ceedings of the tenth ACM international conference on web search and data mining, pages 601-610, 2017. Data available at: http://snap.stanford.edu/data#temporal. doi: 10.1145/3018661.3018731. · doi:10.1145/3018661.3018731 |
| [39] | F. Peruani and L. Tabourier. Directedness of information flow in mobile phone communication networks. PloS one, 6(12):e28860, 2011. doi:10.1371/journal.pone.0028860. · doi:10.1371/journal.pone.0028860 |
| [40] | R. A. Rossi and N. K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. Data available at: https://networkrepository.com/ temporal-networks.php. doi:10.1609/aaai.v29i1.9277. · doi:10.1609/aaai.v29i1.9277 |
| [41] | S. Sun, Y. Wang, W. Liao, and W. Wang. Mining maximal cliques on dynamic graphs effi-ciently by local strategies. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pages 115-118. IEEE, 2017. doi:10.1109/ICDE.2017.53. · doi:10.1109/ICDE.2017.53 |
| [42] | E. Tomita, A. Tanaka, and H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science, 363(1):28-42, 2006. doi:10.1016/j.tcs.2006.06.015. · Zbl 1153.68398 · doi:10.1016/j.tcs.2006.06.015 |
| [43] | P. Vanhems, A. Barrat, C. Cattuto, J.-F. Pinton, N. Khanafer, C. Régis, B.-a. Kim, B. Comte, and N. Voirin. Estimating potential infection transmission routes in hospital wards us-ing wearable proximity sensors. PloS one, 8(9):e73970, 2013. Data available at: http: //www.sociopatterns.org/datasets/hospital-ward-dynamic-contact-network/. doi: 10.1371/journal.pone.0073970. · doi:10.1371/journal.pone.0073970 |
| [44] | T. Viard, M. Latapy, and C. Magnien. Computing maximal cliques in link streams. Theoretical Computer Science, 609:245-252, 2016. doi:10.1016/j.tcs.2015.09.030. · Zbl 1331.68158 · doi:10.1016/j.tcs.2015.09.030 |
| [45] | T. Viard, C. Magnien, and M. Latapy. Enumerating maximal cliques in link streams with durations. Information Processing Letters, 133:44-48, 2018. doi:10.1016/j.ipl.2018.01. 006. · Zbl 1426.68227 · doi:10.1016/j.ipl.2018.01.006 |
| [46] | M. J. Williams and M. Musolesi. Spatio-temporal networks: reachability, centrality and robustness. Royal Society open science, 3(6):160196, 2016. Data available at: https:// datadryad.org/stash/dataset/doi:10.5061/dryad.3p27r. doi:10.1098/rsos.160196. · doi:10.1098/rsos.160196 |
| [47] | X. Zhao, A. Sala, C. Wilson, X. Wang, S. Gaito, H. Zheng, and B. Y. Zhao. Multi-scale dynamics in a massive online social network. In Proceedings of the 2012 Internet Measurement Conference, pages 171-184, 2012. doi:10.1145/2398776.2398795. · doi:10.1145/2398776.2398795 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
