{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T02:03:49Z","timestamp":1762999429753},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T00:00:00Z","timestamp":1545091200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Concerted Research Action"},{"name":"ARC"},{"name":"Federation Wallonia-Brussels Contract","award":["ARC 14\/19-060"],"award-info":[{"award-number":["ARC 14\/19-060"]}]},{"name":"Flagship European Research Area Network"},{"name":"Joint Transnational Call \u2018FuturICT 2.0\u2019"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Several social, medical, engineering and biological challenges rely on discovering the functionality of networks from their structure and node metadata, when it is available. For example, in chemoinformatics one might want to detect whether a molecule is toxic based on structure and atomic types, or discover the research field of a scientific collaboration network. Existing techniques rely on counting or measuring structural patterns that are known to show large variations from network to network, such as the number of triangles, or the assortativity of node metadata. We introduce the concept of multi-hop assortativity, that captures the similarity of the nodes situated at the extremities of a randomly selected path of a given length. We show that multi-hop assortativity unifies various existing concepts and offers a versatile family of \u2018fingerprints\u2019 to characterize networks. These fingerprints allow in turn to recover the functionalities of a network, with the help of the machine learning toolbox. Our method is evaluated empirically on established social and chemoinformatic network benchmarks. Results reveal that our assortativity based features are competitive providing highly accurate results often outperforming state of the art methods for the network classification task.<\/jats:p>","DOI":"10.1093\/comnet\/cny034","type":"journal-article","created":{"date-parts":[[2018,11,23]],"date-time":"2018-11-23T12:09:19Z","timestamp":1542974959000},"page":"603-622","source":"Crossref","is-referenced-by-count":8,"title":["Multi-hop assortativities for network classification"],"prefix":"10.1093","volume":"7","author":[{"given":"Leonardo","family":"Guti\u00e9rrez-G\u00f3mez","sequence":"first","affiliation":[{"name":"Institute for Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM), Universit\u00e9 Catholique de Louvain, Avenue Georges Lema\u00eetre, 4, 1348 Louvain-la-Neuve, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Charles","family":"Delvenne","sequence":"additional","affiliation":[{"name":"Institute for Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM) and Center for Operations Research and Econometrics (CORE), Universit\u00e9 Catholique de Louvain, Avenue Georges Lema\u00eetre, 4, 1348 Louvain-la-Neuve, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"key":"2019081409151473800_B1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","article-title":"The structure and function of complex networks","volume":"45","author":"Newman","year":"2003","journal-title":"SIAM Rev."},{"key":"2019081409151473800_B2","doi-asserted-by":"crossref","first-page":"12917","DOI":"10.1073\/pnas.192407699","article-title":"Food-web structure and network theory: the role of connectance and size","volume":"99","author":"Dunne","year":"2002","journal-title":"Proc. Natl. Acad. Sci."},{"key":"2019081409151473800_B3","first-page":"221","volume-title":"The Stability of a Graph Partition: A Dynamics-Based Framework for Community Detection.","author":"Delvenne","year":"2013"},{"key":"2019081409151473800_B4","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","article-title":"The anatomy of a large-scale hypertextual Web search engine","volume":"30","author":"Brin","year":"1998","journal-title":"Comput. Netw. ISDN Syst."},{"key":"2019081409151473800_B5","first-page":"1","article-title":"Statistical comparisons of classifiers over multiple data sets","volume":"7","author":"Demsar","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"2019081409151473800_B6","volume-title":"Fifth IEEE International Conference on Data Mining ICDM\u201905","author":"Borgwardt","year":"2005"},{"key":"2019081409151473800_B7","first-page":"321","volume-title":"Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21\u201324, 2003","author":"Kashima","year":"2003"},{"key":"2019081409151473800_B8","first-page":"65","article-title":"Expressivity versus efficiency of graph kernels","author":"Ramon","year":"2003","journal-title":"Proceedings of the First International Workshop on Mining Graphs, Trees and Sequences"},{"key":"2019081409151473800_B9","volume-title":"NIPS","author":"Shervashidze","year":"2009"},{"key":"2019081409151473800_B10","first-page":"2539","article-title":"Weisfeiler\u2013Lehman Graph Kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"2019081409151473800_B11","first-page":"791","volume-title":"Cyclic Pattern Kernels Revisited","author":"Horv\u00e1th","year":"2005"},{"key":"2019081409151473800_B12","first-page":"488","volume-title":"JMLR Workshop and Conference Proceedings Volume 5: AISTATS 2009","author":"Shervashidze","year":"2009"},{"key":"2019081409151473800_B13","first-page":"255","volume-title":"Proceedings of the 26th International Conference on Machine Learning, International Conference on Machine Learning, Haifa, Israel, 21\u201324 June 2010","author":"Costa","year":"2010"},{"key":"2019081409151473800_B14","doi-asserted-by":"crossref","first-page":"1365","DOI":"10.1145\/2783258.2783417","volume-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD\u201915","author":"Yanardag","year":"2015"},{"key":"2019081409151473800_B15","article-title":"Efficient estimation of word representations in vector space","author":"Mikolov","year":"2013","journal-title":"CoRR"},{"key":"2019081409151473800_B16","first-page":"2014","article-title":"Learning convolutional neural networks for graphs","volume":"48","author":"Niepert","year":"2016","journal-title":"Proceedings of the 33rd International Conference on International Conference on Machine Learning (ICML\u201916)"},{"key":"2019081409151473800_B17","doi-asserted-by":"crossref","first-page":"42","DOI":"10.3389\/frobt.2018.00042","article-title":"Shift aggregate extract networks","volume":"5","author":"Orsini","year":"2018","journal-title":"Frontiers in Robotics and AI"},{"key":"2019081409151473800_B18","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s00180-012-0381-6","article-title":"Spectral graph features for the classification of graphs and graph sequences","volume":"29","author":"Schmidt","year":"2014","journal-title":"Comput. Stat."},{"key":"2019081409151473800_B19","doi-asserted-by":"crossref","first-page":"1112","DOI":"10.1109\/TPAMI.2005.145","article-title":"Pattern vectors from algebraic graph theory","volume":"27","author":"Wilson","year":"2005","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"2019081409151473800_B20","author":"Barnett","year":"2016","journal-title":"Feature-based classification of networks"},{"key":"2019081409151473800_B21","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","article-title":"\u03bb 1, Isoperimetric inequalities for graphs, and superconcentrators","volume":"38","author":"Alon","year":"1985","journal-title":"J. Comb. Theory B"},{"key":"2019081409151473800_B22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00026-005-0237-z","article-title":"Laplacians and the Cheeger inequality for directed graphs","volume":"9","author":"Chung","year":"2005","journal-title":"Ann. Comb."},{"key":"2019081409151473800_B23","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1109\/TNSE.2015.2391998","article-title":"Random walks, Markov processes and the multiscale modular organization of complex networks","volume":"1","author":"Lambiotte","year":"2014","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"2019081409151473800_B24","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1177\/001316446002000104","article-title":"A coefficient of agreement for nominal scales","volume":"20","author":"Cohen","year":"1960","journal-title":"Educ. Psychol. Meas."},{"key":"2019081409151473800_B25","volume-title":"Entropy and Information Theory","author":"Gray"},{"key":"2019081409151473800_B26","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1038\/163688a0","article-title":"Measurement of diversity","volume":"163","author":"Simpson","year":"1949","journal-title":"Nature"},{"key":"2019081409151473800_B27","doi-asserted-by":"crossref","first-page":"036104","DOI":"10.1103\/PhysRevE.74.036104","article-title":"Finding community structure in networks using the eigenvectors of matrices","volume":"74","author":"Newman","year":"2006","journal-title":"Phys. Rev. E"},{"key":"2019081409151473800_B28","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1145\/990308.990313","article-title":"On clusterings: good, bad and spectral","volume":"51","author":"Kannan","year":"2004","journal-title":"J. ACM"},{"key":"2019081409151473800_B29","first-page":"849","article-title":"On spectral clustering: analysis and an algorithm","volume-title":"Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, NIPS\u201901","author":"Ng","year":"2001"},{"key":"2019081409151473800_B30","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/S0378-8733(01)00038-7","article-title":"Eigenvector-like measures of centrality for asymmetric relations","volume":"23","author":"Bonacich","year":"2001","journal-title":"Soc. Netw."},{"key":"2019081409151473800_B31","first-page":"199","article-title":"A tutorial on support vector regression. A tutorial on support vector regression","author":"Smola","year":"2004","journal-title":"Statistics and Computing 14, 3 (August 2004)"},{"key":"2019081409151473800_B32","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1010933404324","article-title":"Random forests","volume":"45","author":"Breiman","year":"2001","journal-title":"Mach. Learn."},{"key":"2019081409151473800_B33","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1021\/jm00106a046","article-title":"Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity","volume":"34","author":"Debnath","year":"1991","journal-title":"J. Med. Chem."},{"key":"2019081409151473800_B34","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1093\/bioinformatics\/17.1.107","article-title":"The predictive toxicology challenge 2000\u20132001","volume":"17","author":"Helma","year":"2001","journal-title":"Bioinformatics"},{"key":"2019081409151473800_B35","volume-title":"Sixth International Conference on Data Mining (ICDM\u201906)","author":"Wale","year":"2006"},{"key":"2019081409151473800_B36","doi-asserted-by":"crossref","first-page":"i47","DOI":"10.1093\/bioinformatics\/bti1007","article-title":"Protein function prediction via graph kernels","volume":"21","author":"Borgwardt","year":"2005","journal-title":"Bioinformatics"},{"key":"2019081409151473800_B37","doi-asserted-by":"crossref","first-page":"D431","DOI":"10.1093\/nar\/gkh081","article-title":"BRENDA, the enzyme database: updates and major new developments","volume":"32","author":"Schomburg","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2019081409151473800_B38","first-page":"144","volume-title":"Kernels and Regularization on Graphs","author":"Smola"},{"key":"2019081409151473800_B39","first-page":"129","volume-title":"Conference on Learning Theory","author":"G\u00e4rtner","year":"2003"},{"key":"2019081409151473800_B40","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1214\/aoms\/1177731944","article-title":"A comparison of alternative tests of significance for the problem of m rankings","volume":"11","author":"Friedman","year":"1940","journal-title":"Ann. Math. Stat."},{"key":"2019081409151473800_B41","volume-title":"Ph.D. thesis","author":"Nemenyi","year":"1963"},{"key":"2019081409151473800_B42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2017.07.007","article-title":"Random walks and diffusion on networks","volume":"716\u2013717","author":"Masuda","year":"2017","journal-title":"Phys. Rep."},{"key":"2019081409151473800_B43","volume-title":"2018 19th IEEE Mediterranean Electrotechnical Conference (MELECON)","author":"Chi\u00eam","year":"2018"},{"key":"2019081409151473800_B44","doi-asserted-by":"crossref","first-page":"e159","DOI":"10.1371\/journal.pbio.0060159","article-title":"Mapping the structural core of human cerebral cortex","volume":"6","author":"Hagmann","year":"2008","journal-title":"PLoS Biol."}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/advance-article-pdf\/doi\/10.1093\/comnet\/cny034\/27185046\/cny034.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/7\/4\/603\/29161051\/cny034.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,15]],"date-time":"2019-08-15T02:46:48Z","timestamp":1565837208000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/7\/4\/603\/5252051"}},"subtitle":[],"editor":[{"given":"Matjaz","family":"Perc","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2018,12,18]]},"references-count":44,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,12,18]]},"published-print":{"date-parts":[[2019,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cny034","relation":{},"ISSN":["2051-1329"],"issn-type":[{"value":"2051-1329","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,8]]},"published":{"date-parts":[[2018,12,18]]}}}