{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:59Z","timestamp":1750220279757,"version":"3.41.0"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ministry of Education and Science of the Russian Federation in the framework of MegaGrant","award":["075-15-2019-1926"],"award-info":[{"award-number":["075-15-2019-1926"]}]},{"name":"Russian President","award":["NSh-2540.2020.1."],"award-info":[{"award-number":["NSh-2540.2020.1."]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>Information diffusion, spreading of infectious diseases, and spreading of rumors are fundamental processes occurring in real-life networks. In many practical cases, one can observe when nodes become infected, but the underlying network, over which a contagion or information propagates, is hidden. Inferring properties of the underlying network is important since these properties can be used for constraining infections, forecasting, viral marketing, and so on. Moreover, for many applications, it is sufficient to recover only coarse high-level properties of this network rather than all its edges. This article conducts a systematic and extensive analysis of the following problem: Given only the infection times, find communities of highly interconnected nodes. This task significantly differs from the well-studied community detection problem since we do not observe a graph to be clustered. We carry out a thorough comparison between existing and new approaches on several large datasets and cover methodological challenges specific to this problem. One of the main conclusions is that the most stable performance and the most significant improvement on the current state-of-the-art are achieved by our proposed simple heuristic approaches agnostic to a particular graph structure and epidemic model. We also show that some well-known community detection algorithms can be enhanced by including edge weights based on the cascade data.<\/jats:p>","DOI":"10.1145\/3494563","type":"journal-article","created":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T20:51:00Z","timestamp":1641675060000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["When Less Is More: Systematic Analysis of Cascade-Based Community Detection"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1520-4167","authenticated-orcid":false,"given":"Liudmila","family":"Prokhorenkova","sequence":"first","affiliation":[{"name":"Yandex Research, MIPT, HSE University, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexey","family":"Tikhonov","sequence":"additional","affiliation":[{"name":"Yandex, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6750-3484","authenticated-orcid":false,"given":"Nelly","family":"Litvak","sequence":"additional","affiliation":[{"name":"University of Twente, Eindhoven University of Technology, Enschede, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,1,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1134271.1134277"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/05\/P05001"},{"key":"e_1_3_2_4_2","volume-title":"Proceedings of the 4th ACM International Conference on Web Seach and Data Mining","author":"Bakshy Eytan","year":"2011","unstructured":"Eytan Bakshy, Jake M. Hofman, Winter A. Mason, and Duncan J. Watts. 2011. Identifying influencers on twitter. In Proceedings of the 4th ACM International Conference on Web Seach and Data Mining."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433403"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.164"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2979682"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3091106"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/asi.22986"},{"key":"e_1_3_2_11_2","volume-title":"Proceedings of the 5th International AAAI Conference on Weblogs and Social Media","author":"Conover Michael D","year":"2011","unstructured":"Michael D Conover, Jacob Ratkiewicz, Matthew Francisco, Bruno Gon\u00e7alves, Filippo Menczer, and Alessandro Flammini. 2011. Political polarization on twitter. In Proceedings of the 5th International AAAI Conference on Weblogs and Social Media."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/sam.10133"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/3044805.3044981"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/2999325.2999445"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.09.002"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/1863190.1863193"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/276675.276685"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/3104482.3104553"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2014.3"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835933"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/3042817.3043011"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433402"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/3042573.3042776"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2020.0936"},{"key":"e_1_3_2_27_2","article-title":"Systematic analysis of cluster similarity indices: How to validate validation measures","author":"G\u00f6sgens Martijn","year":"2021","unstructured":"Martijn G\u00f6sgens, Liudmila Prokhorenkova, and Alexey Tikhonov. 2021. Systematic analysis of cluster similarity indices: How to validate validation measures. In Proceedings of the International Conference on Machine Learning.","journal-title":"Proceedings of the International Conference on Machine Learning"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSIPN.2020.2990276"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/3120828.3120877"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2021.3091638"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1126\/sciadv.aav1478"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0308344101"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.016107"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2005.0051"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2020.00323"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"e_1_3_2_39_2","article-title":"Social contagion: An empirical study of information spread on digg and twitter follower graphs","author":"Lerman Kristina","year":"2013","unstructured":"Kristina Lerman, Rumi Ghosh, and Tawan Surachawala. 2013. Social contagion: An empirical study of information spread on digg and twitter follower graphs. arXiv:1202.3162. Retrieved from https:\/\/arxiv.org\/abs\/1202.3162.","journal-title":"arXiv:1202.3162. Retrieved from https:\/\/arxiv.org\/abs\/1202.3162"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_3_2_41_2","article-title":"Unsupervised community detection with modularity-based attention model","author":"Lobov Ivan","year":"2019","unstructured":"Ivan Lobov and Sergey Ivanov. 2019. Unsupervised community detection with modularity-based attention model. arXiv:1905.10350.Retrieved from https:\/\/arxiv.org\/abs\/1905.10350.","journal-title":"arXiv:1905.10350."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00265-003-0651-y"},{"key":"e_1_3_2_43_2","unstructured":"Xiaoxiao Ma Jia Wu Shan Xue Jian Yang Quan Z Sheng Hui Xiong and Leman Akoglu. 2021. A comprehensive survey on graph anomaly detection with deep learning. IEEE Transactions on Knowledge and Data Engineering ."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-020-16285-7"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009953814988"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/2997046.2997090"},{"key":"e_1_3_2_47_2","article-title":"Community detection in networks: Modularity optimization and maximum likelihood are equivalent","author":"Newman M. E. J.","year":"2016","unstructured":"M. E. J. Newman. 2016. Community detection in networks: Modularity optimization and maximum likelihood are equivalent. arXiv:1606.02319. Retrieved from https:\/\/arxiv.org\/abs\/1606.02319.","journal-title":"arXiv:1606.02319. Retrieved from https:\/\/arxiv.org\/abs\/1606.02319."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1140\/epjp\/s13360-020-00541-2"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.110.148701"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.123.128301"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313429"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313560"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3110215"},{"key":"e_1_3_2_56_2","article-title":"DANI: A fast diffusion aware network inference algorithm","author":"Ramezani Maryam","year":"2017","unstructured":"Maryam Ramezani, Hamid R Rabiee, Maryam Tahani, and Arezoo Rajabi. 2017. DANI: A fast diffusion aware network inference algorithm. arXiv:1706.00941. Retrieved from https:\/\/arxiv.org\/abs\/1706.00941.","journal-title":"arXiv:1706.00941. Retrieved from https:\/\/arxiv.org\/abs\/1706.00941."},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963503"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1939"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2018.01.004"},{"key":"e_1_3_2_61_2","article-title":"A comprehensive survey on community detection with deep learning","author":"Su Xing","year":"2021","unstructured":"Xing Su, Shan Xue, Fanzhen Liu, Jia Wu, Jian Yang, Chuan Zhou, Wenbin Hu, Cecile Paris, Surya Nepal, Di Jin, Quan Z. Sheng, and Philip S. Yu. 2021. A comprehensive survey on community detection with deep learning. arXiv:2105.12584. Retrieved from https:\/\/arxiv.org\/abs\/2105.12584.","journal-title":"arXiv:2105.12584."},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81854-8_1"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.5555\/784591.784730"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"e_1_3_2_65_2","article-title":"Detecting communities in a gossip model with stubborn agents","author":"Xing Yu","year":"2021","unstructured":"Yu Xing, Xingkang He, Haitao Fang, and Karl H Johansson. 2021. Detecting communities in a gossip model with stubborn agents. arXiv:2102.09683. Retrieved from https:\/\/arxiv.org\/abs\/2102.09683.","journal-title":"arXiv:2102.09683."},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.5555\/1764441.1764561"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373464.3373473"},{"key":"e_1_3_2_69_2","first-page":"4342","volume-title":"International Conference on Machine Learning","author":"Hoffmann Jessica","year":"2020","unstructured":"Jessica Hoffmann, Soumya Basu, Surbhi Goel, and Constantine Caramanis. 2020. Learning mixtures of graphs from epidemic cascades. In International Conference on Machine Learning. PMLR, 4342\u20134352."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494563","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494563","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494563"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,8]]},"references-count":68,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3494563"],"URL":"https:\/\/doi.org\/10.1145\/3494563","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2022,1,8]]},"assertion":[{"value":"2021-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}