{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T20:24:02Z","timestamp":1772828642001,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T00:00:00Z","timestamp":1636675200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T00:00:00Z","timestamp":1636675200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004004","name":"Universit\u00e0 degli Studi di Trento","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004004","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Temporal graphs are structures which model relational data between entities that change over time. Due to the complex structure of data, mining statistically significant temporal subgraphs, also known as temporal motifs, is a challenging task. In this work, we present an efficient technique for extracting temporal motifs in temporal networks. Our method is based on the novel notion of egocentric temporal neighborhoods, namely multi-layer structures centered on an ego node. Each temporal layer of the structure consists of the first-order neighborhood of the ego node, and corresponding nodes in sequential layers are connected by an edge. The strength of this approach lies in the possibility of encoding these structures into a unique bit vector, thus bypassing the problem of graph isomorphism in searching for temporal motifs. This allows our algorithm to mine substantially larger motifs with respect to alternative approaches. Furthermore, by bringing the focus on the temporal dynamics of the interactions of a specific node, our model allows to mine temporal motifs which are visibly interpretable. Experiments on a number of complex networks of social interactions confirm the advantage of the proposed approach over alternative non-egocentric solutions. The egocentric procedure is indeed more efficient in revealing similarities and discrepancies among different social environments, independently of the different technologies used to collect data, which instead affect standard non-egocentric measures.<\/jats:p>","DOI":"10.1007\/s10618-021-00803-2","type":"journal-article","created":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T09:04:13Z","timestamp":1636707853000},"page":"355-378","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["An efficient procedure for mining egocentric temporal motifs"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0337-1838","authenticated-orcid":false,"given":"Antonio","family":"Longa","sequence":"first","affiliation":[]},{"given":"Giulia","family":"Cencetti","sequence":"additional","affiliation":[]},{"given":"Bruno","family":"Lepri","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Passerini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,12]]},"reference":[{"issue":"6","key":"803_CR1","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/j.pmcj.2011.09.004","volume":"7","author":"N Aharony","year":"2011","unstructured":"Aharony N, Pan W, Ip C, Khayal I, Pentland A (2011) Social fmri: investigating and shaping social mechanisms in the real world. Pervasive Mob Comput 7(6):643\u2013659","journal-title":"Pervasive Mob Comput"},{"issue":"6","key":"803_CR2","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1038\/nrg2102","volume":"8","author":"U Alon","year":"2007","unstructured":"Alon U (2007) Network motifs: theory and experimental approaches. Nat Rev Genet 8(6):450\u2013461","journal-title":"Nat Rev Genet"},{"key":"803_CR3","doi-asserted-by":"crossref","unstructured":"Araujo M, Papadimitriou S, G\u00fcnnemann S, Faloutsos C, Basu P, Swami A, Papalexakis EE, Koutra D (2014) Com2: fast automatic discovery of temporal (\u2018comet\u2019) communities. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, pp. 271\u2013283","DOI":"10.1007\/978-3-319-06605-9_23"},{"issue":"5439","key":"803_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A-L Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509\u2013512","journal-title":"Science"},{"key":"803_CR5","unstructured":"Berlingerio M, Koutra D, Eliassi-Rad T, Faloutsos C (2012) Netsimile: a scalable approach to size-independent network similarity. arXiv preprint arXiv:1209.2684"},{"key":"803_CR6","first-page":"132","volume":"3","author":"B Bollob\u00e1s","year":"2003","unstructured":"Bollob\u00e1s B, Borgs C, Chayes JT, Riordan O (2003) Directed scale-free graphs. SODA 3:132\u2013139","journal-title":"Directed scale-free graphs. SODA"},{"issue":"2","key":"803_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1921632.1921636","volume":"5","author":"DM Dunlavy","year":"2011","unstructured":"Dunlavy DM, Kolda TG, Acar E (2011) Temporal link prediction using matrix and tensor factorizations. ACM Trans Knowl Discov Data (TKDD) 5(2):1\u201327","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"issue":"1","key":"803_CR8","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s P, R\u00e9nyi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5(1):17\u201360","journal-title":"Publ Math Inst Hung Acad Sci"},{"issue":"9","key":"803_CR9","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0107878","volume":"9","author":"J Fournet","year":"2014","unstructured":"Fournet J, Barrat A (2014) Contact patterns among high school students. PLoS ONE 9(9):e107878. https:\/\/doi.org\/10.1371\/journal.pone.0107878","journal-title":"PLoS ONE"},{"issue":"3","key":"803_CR10","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1017\/nws.2015.10","volume":"3","author":"M G\u00e9nois","year":"2015","unstructured":"G\u00e9nois M, Vestergaard CL, Fournet J, Panisson A, Bonmarin I, Barrat A (2015) Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers. Netw Sci 3(3):326\u2013347","journal-title":"Netw Sci"},{"key":"803_CR11","doi-asserted-by":"crossref","unstructured":"Gurukar S, Ranu S, Ravindran B (2015) Commit: a scalable approach to mining communication motifs from dynamic networks. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data, pp 475\u2013489","DOI":"10.1145\/2723372.2737791"},{"issue":"9","key":"803_CR12","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1140\/epjb\/e2015-60657-4","volume":"88","author":"P Holme","year":"2015","unstructured":"Holme P (2015) Modern temporal network theory: a colloquium. Eur Phys J B 88(9):234","journal-title":"Eur Phys J B"},{"issue":"3","key":"803_CR13","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme P, Saramaki J (2012) Temporal networks. Phys Rep 519(3):97\u2013125","journal-title":"Phys Rep"},{"issue":"12","key":"803_CR14","doi-asserted-by":"publisher","first-page":"i171","DOI":"10.1093\/bioinformatics\/btv227","volume":"31","author":"Y Hulovatyy","year":"2015","unstructured":"Hulovatyy Y, Chen H, Milenkovi\u0107 T (2015) Exploring the structure and function of temporal networks with dynamic graphlets. Bioinformatics 31(12):i171\u2013i180","journal-title":"Bioinformatics"},{"key":"803_CR15","doi-asserted-by":"crossref","unstructured":"Jazayeri A, Yang CC (2020) Motif discovery algorithms in static and temporal networks: a survey. arXiv preprint arXiv:2005.09721","DOI":"10.1093\/comnet\/cnaa031"},{"key":"803_CR16","doi-asserted-by":"crossref","unstructured":"Jin R, McCallen S, Almaas E (2007) Trend motif: a graph mining approach for analysis of dynamic complex networks. In: Seventh IEEE international conference on data mining (ICDM 2007). IEEE, pp. 541\u2013546","DOI":"10.1109\/ICDM.2007.92"},{"issue":"5757","key":"803_CR17","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1126\/science.1116869","volume":"311","author":"G Kossinets","year":"2006","unstructured":"Kossinets G, Watts D (2006) Empirical analysis of an evolving social network. Science 311(5757):88\u201390","journal-title":"Science"},{"key":"803_CR18","doi-asserted-by":"crossref","unstructured":"Kossinets G, Kleinberg J, Watts D (2008) The structure of information pathways in a social communication network. In: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 435\u2013443","DOI":"10.1145\/1401890.1401945"},{"issue":"6","key":"803_CR19","doi-asserted-by":"publisher","first-page":"1840","DOI":"10.1007\/s10618-017-0515-0","volume":"31","author":"O Kostakis","year":"2017","unstructured":"Kostakis O, Tatti N, Gionis A (2017) Discovering recurring activity in temporal networks. Data Min Knowl Disc 31(6):1840\u20131871","journal-title":"Data Min Knowl Disc"},{"key":"803_CR20","unstructured":"Kosyfaki C, Mamoulis N, Pitoura E, Tsaparas P (2018) Flow motifs in interaction networks. arXiv preprint arXiv:1810.08408"},{"key":"803_CR21","doi-asserted-by":"publisher","first-page":"P11005","DOI":"10.1088\/1742-5468\/2011\/11\/P11005","volume":"11","author":"L Kovanen","year":"2011","unstructured":"Kovanen L, Karsai M, Kaski K, Kert\u00e9sz J (2011) Saram\u00e4ki J (2011) Temporal motifs in time-dependent networks. J Stat Mech: Theory Exp 11:P11005","journal-title":"J Stat Mech: Theory Exp"},{"key":"803_CR22","doi-asserted-by":"crossref","unstructured":"Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data (TKDD), 1(1):2\u2013es","DOI":"10.1145\/1217299.1217301"},{"key":"803_CR23","doi-asserted-by":"crossref","unstructured":"Liu P, Benson AR, Charikar M (2019) Sampling methods for counting temporal motifs. In: Proceedings of the twelfth ACM international conference on web search and data mining, pp 294\u2013302","DOI":"10.1145\/3289600.3290988"},{"issue":"9","key":"803_CR24","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0136497","volume":"10","author":"R Mastrandrea","year":"2015","unstructured":"Mastrandrea R, Fournet J, Barrat A (2015) Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys. PLoS ONE 10(9):e0136497","journal-title":"PLoS ONE"},{"issue":"1","key":"803_CR25","first-page":"60","volume":"2","author":"S Milgram","year":"1967","unstructured":"Milgram S (1967) The small world problem. Psychol Today 2(1):60\u201367","journal-title":"The small world problem. Psychol Today"},{"issue":"5594","key":"803_CR26","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: simple building blocks of complex networks. Science 298(5594):824\u2013827","journal-title":"Science"},{"key":"803_CR27","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Network: an introduction","author":"M Newman","year":"2010","unstructured":"Newman M (2010) Network: an introduction. Oxford University Press, Oxford"},{"key":"803_CR28","doi-asserted-by":"crossref","unstructured":"Nicosia V, Tang J, Mascolo C, Musolesi M, Russo G, Latora V (2013) Graph metrics for temporal networks. In: Temporal networks. Springer, pp 15\u201340","DOI":"10.1007\/978-3-642-36461-7_2"},{"key":"803_CR29","doi-asserted-by":"crossref","unstructured":"Paranjape A, Benson AR, Leskovec J (2017) Motifs in temporal networks. In: Proceedings of the tenth ACM international conference on web search and data mining, pp 601\u2013610","DOI":"10.1145\/3018661.3018731"},{"key":"803_CR30","unstructured":"Ray A, Holder L, Choudhury S (2014) Frequent subgraph discovery in large attributed streaming graphs. In: Proceedings of the 3rd international workshop on big data, streams and heterogeneous source mining: algorithms, systems, programming models and applications, pp 166\u2013181"},{"key":"803_CR31","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: AAAI. http:\/\/networkrepository.com","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"3","key":"803_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3046791","volume":"11","author":"P Rozenshtein","year":"2017","unstructured":"Rozenshtein P, Tatti N, Gionis A (2017) Finding dynamic dense subgraphs. ACM Trans Knowl Discov Data (TKDD) 11(3):1\u201330","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"key":"803_CR33","doi-asserted-by":"crossref","unstructured":"Rozenshtein P, Preti G, Gionis A, Velegrakis Y (2020) Mining dense subgraphs with similar edges. arXiv preprint arXiv:2007.03950","DOI":"10.1007\/978-3-030-67664-3_2"},{"issue":"1","key":"803_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41597-019-0325-x","volume":"6","author":"P Sapiezynski","year":"2019","unstructured":"Sapiezynski P, Stopczynski A, Lassen DD, Lehmann S (2019) Interaction data from the Copenhagen networks study. Sci Data 6(1):1\u201310","journal-title":"Sci Data"},{"issue":"8","key":"803_CR35","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0023176","volume":"6","author":"J Stehl\u00e9","year":"2011","unstructured":"Stehl\u00e9 J, Voirin N, Barrat A, Cattuto C, Isella L, Pinton J-F, Quaggiotto M, Van den Broeck W, R\u00e9gis C, Lina B et al (2011) High-resolution measurements of face-to-face contact patterns in a primary school. PLoS ONE 6(8):e23176","journal-title":"PLoS ONE"},{"key":"803_CR36","doi-asserted-by":"crossref","unstructured":"Tantipathananandh C, Berger-Wolf T, Kempe D (2007) A framework for community identification in dynamic social networks. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 717\u2013726","DOI":"10.1145\/1281192.1281269"},{"issue":"2","key":"803_CR37","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1001\/archinternmed.2010.500","volume":"171","author":"P Vanhems","year":"2011","unstructured":"Vanhems P, Voirin N, Roche S, Escuret V, Regis C, Gorain C, Pires-Cronenberger S, Giard M, Lina B, Najioullah F et al (2011) Risk of influenza-like illness in an acute health care setting during community influenza epidemics in 2004\u20132005, 2005\u20132006, and 2006\u20132007: a prospective study. Arch Intern Med 171(2):151\u2013157","journal-title":"Arch Intern Med"},{"issue":"9","key":"803_CR38","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0073970","volume":"8","author":"P Vanhems","year":"2013","unstructured":"Vanhems P, Barrat A, Cattuto C, Pinton J-F, Khanafer N, R\u00e9gis C, Kim B-A, Comte B, Voirin N (2013) Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PLoS ONE 8(9):e73970","journal-title":"PLoS ONE"},{"key":"803_CR39","doi-asserted-by":"crossref","unstructured":"Wang J, Wang Y, Jiang W, Li Y, Tan K-L (2020) Efficient sampling algorithms for approximate temporal motif counting. In: Proceedings of the 29th ACM international conference on information & knowledge management, pp 1505\u20131514","DOI":"10.1145\/3340531.3411862"},{"key":"803_CR40","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478","volume-title":"Social network analysis: methods and applications","author":"S Wasserman","year":"1994","unstructured":"Wasserman S, Faust K et al (1994) Social network analysis: methods and applications, vol 8. Cambridge University Press, Cambridge"},{"key":"803_CR41","doi-asserted-by":"crossref","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684):440\u2013442","DOI":"10.1038\/30918"},{"key":"803_CR42","doi-asserted-by":"crossref","unstructured":"Zhao Q, Tian Y, He Q, Oliver N, Jin R, Lee W-C (2010) Communication motifs: a tool to characterize social communications. In: Proceedings of the 19th ACM international conference on Information and knowledge management, pp 1645\u20131648","DOI":"10.1145\/1871437.1871694"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00803-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-021-00803-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00803-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,15]],"date-time":"2023-01-15T02:12:23Z","timestamp":1673748743000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-021-00803-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,12]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["803"],"URL":"https:\/\/doi.org\/10.1007\/s10618-021-00803-2","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,12]]},"assertion":[{"value":"23 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}