{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T04:07:26Z","timestamp":1729742846079,"version":"3.28.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T00:00:00Z","timestamp":1687824000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T00:00:00Z","timestamp":1687824000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NSF CAREER","award":["DMS-2141621"],"award-info":[{"award-number":["DMS-2141621"]}]},{"name":"NSF RTG grant","award":["DMS-2134107","DMS-2134107","DMS-2134107"],"award-info":[{"award-number":["DMS-2134107","DMS-2134107","DMS-2134107"]}]},{"name":"NSF","award":["DMS-2113662","DMS-2113662"],"award-info":[{"award-number":["DMS-2113662","DMS-2113662"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the statistical learning of nodal attribute functionals in homophily networks using random walks. Attributes can be discrete or continuous. A generalization of various existing canonical models, based on preferential attachment is studied (model class<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {P}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>P<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>), where new nodes form connections dependent on both their attribute values and popularity as measured by degree. An associated model class<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {U}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>U<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is described, which is amenable to theoretical analysis and gives access to asymptotics of a host of functionals of interest. Settings where asymptotics for model class<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {U}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>U<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>transfer over to model class<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {P}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>P<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>through the phenomenon of resolvability are analyzed. For the statistical learning, we consider several canonical attribute agnostic sampling schemes such as Metropolis-Hasting random walk, versions of node2vec (Grover and Leskovec, 2016) that incorporate both classical random walk and non-backtracking propensities and propose new variants which use attribute information in addition to topological information to explore the network. Estimators for learning the attribute distribution, degree distribution for an attribute type and homophily measures are proposed. The performance of such statistical learning framework is studied on both synthetic networks (model class<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {P}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>P<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) and real world systems, and its dependence on the network topology, degree of homophily or absence thereof, (un)balanced attributes, is assessed.<\/jats:p>","DOI":"10.1007\/s41109-023-00558-3","type":"journal-article","created":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T11:02:11Z","timestamp":1687863731000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Learning attribute and homophily measures through random walks"],"prefix":"10.1007","volume":"8","author":[{"given":"Nelson","family":"Antunes","sequence":"first","affiliation":[]},{"given":"Sayan","family":"Banerjee","sequence":"additional","affiliation":[]},{"given":"Shankar","family":"Bhamidi","sequence":"additional","affiliation":[]},{"given":"Vladas","family":"Pipiras","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,27]]},"reference":[{"key":"558_CR1","unstructured":"Aldous D, Fill J.A (2002) Reversible Markov Chains and Random Walks on Graphs. Unfinished monograph, recompiled 2014 http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html"},{"key":"558_CR2","unstructured":"Antunes N, Banerjee S, Bhamidi S, Pipiras V (2023a) Attribute network models, stochastic approximation, and network sampling and ranking. Preprint arXiv:2304.08565v1"},{"key":"558_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-031-21131-7_2","volume-title":"Complex networks and their applications XI","author":"N Antunes","year":"2023","unstructured":"Antunes N, Bhamidi S, Pipiras V (2023b) Learning attribute distributions through random walks. In: Cherifi H, Mantegna RN, Rocha LM, Cherifi C, Micciche S (eds) Complex networks and their applications XI. Springer, Cham, pp 17\u201329"},{"key":"558_CR4","doi-asserted-by":"crossref","unstructured":"Antunes N, Bhamidi S, Guo T, Pipiras V, Wang B (2021a) Sampling based estimation of in-degree distribution for directed complex networks. J Comput Gr Stat 30(4):863\u2013876","DOI":"10.1080\/10618600.2021.1873143"},{"key":"558_CR5","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1017\/nws.2021.2","volume":"9","author":"N Antunes","year":"2021","unstructured":"Antunes N, Guo T, Pipiras V (2021b) Sampling methods and estimation of triangle count distributions in large networks. Netw Sci 9:134\u2013156","journal-title":"Netw Sci"},{"issue":"04","key":"558_CR6","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1142\/S0219199707002551","volume":"09","author":"N Alon","year":"2007","unstructured":"Alon N, Benjamini I, Lubetzky E, Sodin S (2007) Non-backtracking random walks mix faster. Commun Contem Math 09(04):585\u2013603","journal-title":"Commun Contem Math"},{"issue":"5439","key":"558_CR7","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":"558_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Hamou A, Lubetzky E, Peres Y (2018) Comparing mixing times on sparse random graphs. In: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pp 1734\u20131740. SIAM","DOI":"10.1137\/1.9781611975031.113"},{"key":"558_CR9","doi-asserted-by":"crossref","unstructured":"Baroni A, Conte A, Patrignani M, Ruggieri S (2017) Efficiently clustering very large attributed graphs. In: 2017 IEEE\/ACM international conference on advances in social networks analysis and mining (ASONAM), pp 369\u2013376","DOI":"10.1145\/3110025.3110030"},{"key":"558_CR10","doi-asserted-by":"crossref","unstructured":"Berahmand K, Mohammadi M, Saberi-Movahed F, Li Y, Xu Y (2022) Graph regularized nonnegative matrix factorization for community detection in attributed networks. IEEE Trans Netw Sci Eng","DOI":"10.1109\/TNSE.2022.3210233"},{"key":"558_CR11","unstructured":"Banerjee S, Deka P, Olvera-Cravioto M (2023) Local weak limits for collapsed branching processes with random out-degrees. arXiv preprint arXiv:2302.00562"},{"key":"558_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2020.05.004","volume":"874","author":"F Battiston","year":"2020","unstructured":"Battiston F, Cencetti G, Iacopini I, Latora V, Lucas M, Patania A, Young J-G, Petri G (2020) Networks beyond pairwise interactions: structure and dynamics. Phys Rep 874:1\u201392","journal-title":"Phys Rep"},{"issue":"1","key":"558_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/12-AOP755","volume":"42","author":"N Berger","year":"2014","unstructured":"Berger N, Borgs C, Chayes JT, Saberi A (2014) Asymptotic behavior and distributional limits of preferential attachment graphs. Ann Probab 42(1):1\u201340","journal-title":"Ann Probab"},{"issue":"24","key":"558_CR14","doi-asserted-by":"publisher","first-page":"5632","DOI":"10.1103\/PhysRevLett.86.5632","volume":"86","author":"G Bianconi","year":"2001","unstructured":"Bianconi G, Barab\u00e1si A-L (2001) Bose-Einstein condensation in complex networks. Phys Rev Lett 86(24):5632","journal-title":"Phys Rev Lett"},{"issue":"4","key":"558_CR15","doi-asserted-by":"publisher","first-page":"684","DOI":"10.1109\/TNSE.2018.2870671","volume":"6","author":"C-H Chang","year":"2019","unstructured":"Chang C-H, Chang C-S, Chang C-T, Lee D-S, Lu P-E (2019) Exponentially twisted sampling for centrality analysis and community detection in attributed networks. IEEE Trans Netw Sci Eng 6(4):684\u2013697","journal-title":"IEEE Trans Netw Sci Eng"},{"issue":"2","key":"558_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1002\/rsa.20700","volume":"51","author":"N Chen","year":"2017","unstructured":"Chen N, Litvak N, Olvera-Cravioto M (2017) Generalized pagerank on directed configuration networks. Random Struct Algorithms 51(2):237\u2013274","journal-title":"Random Struct Algorithms"},{"issue":"6","key":"558_CR17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.95.062301","volume":"95","author":"OT Courtney","year":"2017","unstructured":"Courtney OT, Bianconi G (2017) Weighted growing simplicial complexes. Phys Rev E 95(6):062301","journal-title":"Phys Rev E"},{"issue":"2","key":"558_CR18","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1140\/epjb\/e2012-30802-x","volume":"86","author":"ML de Almeida","year":"2013","unstructured":"de Almeida ML, Mendes GA, Madras Viswanathan G, da Silva LR (2013) Scale-free homophilic network. Eur Phys J B 86(2):38","journal-title":"Eur Phys J B"},{"key":"558_CR19","doi-asserted-by":"crossref","unstructured":"Esp\u00edn-Noboa L, Karimi F, Ribeiro B, Lerman K, Wagner C (2021) Explaining classification performance and bias via network structure and sampling technique. Appl Netw Sci 6(79)","DOI":"10.1007\/s41109-021-00394-3"},{"key":"558_CR20","doi-asserted-by":"crossref","unstructured":"Esp\u00edn-Noboa L, Wagner C, Strohmaier M, Karimi F (2022) Inequality and inequity in network-based ranking and recommendation algorithms. Sci Rep 12(1), 2012","DOI":"10.1038\/s41598-022-05434-1"},{"issue":"1","key":"558_CR21","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/s10489-020-01825-x","volume":"51","author":"H Fan","year":"2021","unstructured":"Fan H, Zhong Y, Zeng G, Sun L (2021) Attributed network representation learning via improved graph attention with robust negative sampling. Appl Intell 51(1):416\u2013426","journal-title":"Appl Intell"},{"issue":"2261","key":"558_CR22","doi-asserted-by":"publisher","first-page":"20220059","DOI":"10.1098\/rspa.2022.0059","volume":"478","author":"J Fan","year":"2022","unstructured":"Fan J, Yin Q, Xia C, Perc M (2022) Epidemics on multilayer simplicial complexes. Proc R Soc A 478(2261):20220059","journal-title":"Proc R Soc A"},{"issue":"1","key":"558_CR23","first-page":"87","volume":"4","author":"AD Flaxman","year":"2007","unstructured":"Flaxman AD, Frieze AM, Vera J (2007) A geometric preferential attachment model of networks ii. Int Math 4(1):87\u2013111","journal-title":"Int Math"},{"key":"558_CR24","unstructured":"Garavaglia A, Hazra R.S, van der Hofstad R, Ray R (2022) Universality of the local limit of preferential attachment models. arXiv preprint arXiv:2212.05551"},{"key":"558_CR25","doi-asserted-by":"crossref","unstructured":"Grover A, Leskovec J (2016) Node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. KDD \u201916, pp 855\u2013864. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/2939672.2939754"},{"issue":"1","key":"558_CR26","doi-asserted-by":"publisher","first-page":"2485","DOI":"10.1038\/s41467-019-10431-6","volume":"10","author":"I Iacopini","year":"2019","unstructured":"Iacopini I, Petri G, Barrat A, Latora V (2019) Simplicial models of social contagion. Nat Commun 10(1):2485","journal-title":"Nat Commun"},{"key":"558_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/EJP.v18-2271","volume":"18","author":"J Jordan","year":"2013","unstructured":"Jordan J (2013) Geometric preferential attachment in non-uniform metric spaces. Electron J Probab 18:1\u201315","journal-title":"Electron J Probab"},{"issue":"1","key":"558_CR28","doi-asserted-by":"publisher","first-page":"11077","DOI":"10.1038\/s41598-018-29405-7","volume":"8","author":"F Karimi","year":"2018","unstructured":"Karimi F, G\u00e9nois M, Wagner C, Singer P, Strohmaier M (2018) Homophily influences ranking of minorities in social networks. Sci Rep 8(1):11077","journal-title":"Sci Rep"},{"issue":"6","key":"558_CR29","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.63.066123","volume":"63","author":"PL Krapivsky","year":"2001","unstructured":"Krapivsky PL, Redner S (2001) Organization of growing random networks. Phys Rev E 63(6):066123","journal-title":"Phys Rev E"},{"key":"558_CR30","doi-asserted-by":"crossref","unstructured":"Kumar S, Sundaram H (2021) Attribute-guided network sampling mechanisms. ACM Trans Knowl Discov Data 15(4)","DOI":"10.1145\/3441445"},{"key":"558_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-88146-1","volume-title":"Statistical analysis of network data","author":"ED Kolaczyk","year":"2009","unstructured":"Kolaczyk ED (2009) Statistical analysis of network data. Springer, New York"},{"key":"558_CR32","unstructured":"Lee DJL, Han J, Chambourova D, Kumar R (2017) Identifying fashion accounts in social networks. In: Proceedings of the KDD workshop on ML meets fashion"},{"issue":"188","key":"558_CR33","doi-asserted-by":"publisher","first-page":"20220043","DOI":"10.1098\/rsif.2022.0043","volume":"19","author":"S Majhi","year":"2022","unstructured":"Majhi S, Perc M, Ghosh D (2022) Dynamics on higher-order networks: a review. J R Soc Interface 19(188):20220043","journal-title":"J R Soc Interface"},{"issue":"2243","key":"558_CR34","first-page":"20200447","volume":"476","author":"L Meng","year":"2020","unstructured":"Meng L, Masuda N (2020) Analysis of node2vec random walks on networks. Proc R Soc A Math Phys Eng Sci 476(2243):20200447","journal-title":"Proc R Soc A Math Phys Eng Sci"},{"issue":"1","key":"558_CR35","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1146\/annurev.soc.27.1.415","volume":"27","author":"M McPherson","year":"2001","unstructured":"McPherson M, Smith-Lovin L, Cook JM (2001) Birds of a feather: homophily in social networks. Annu Rev Sociol 27(1):415\u2013444","journal-title":"Annu Rev Sociol"},{"key":"558_CR36","doi-asserted-by":"crossref","unstructured":"Mihail M, Papadimitriou C, Saberi A (2003) On certain connectivity properties of the internet topology. In: 44th annual IEEE symposium on foundations of computer science, 2003. Proceedings, pp 28\u201335. IEEE","DOI":"10.1109\/SFCS.2003.1238178"},{"key":"558_CR37","doi-asserted-by":"crossref","unstructured":"Mislove A, Viswanath B, Gummadi KP, Druschel P (2010) You are who you know: inferring user profiles in online social networks. In: Proceedings of the third ACM international conference on web search and data mining, pp 251\u2013260","DOI":"10.1145\/1718487.1718519"},{"issue":"3","key":"558_CR38","doi-asserted-by":"publisher","first-page":"3745","DOI":"10.1007\/s11042-022-12943-8","volume":"82","author":"E Nasiri","year":"2023","unstructured":"Nasiri E, Berahmand K, Li Y (2023) Robust graph regularization nonnegative matrix factorization for link prediction in attributed networks. Multimedia Tools Appl 82(3):3745\u20133768","journal-title":"Multimedia Tools Appl"},{"issue":"46","key":"558_CR39","doi-asserted-by":"publisher","first-page":"17916","DOI":"10.1073\/pnas.0705081104","volume":"104","author":"J Park","year":"2007","unstructured":"Park J, Barab\u00e1si A-L (2007) Distribution of node characteristics in complex networks. Proc Natl Acad Sci 104(46):17916\u201317920","journal-title":"Proc Natl Acad Sci"},{"key":"558_CR40","doi-asserted-by":"crossref","unstructured":"Shrum W, Cheek Jr N.H, Mac DS (1988) Friendship in school: gender and racial homophily. Sociol Educ 2:227\u2013239","DOI":"10.2307\/2112441"},{"issue":"1","key":"558_CR41","doi-asserted-by":"publisher","first-page":"1308","DOI":"10.1038\/s41467-023-37019-5","volume":"14","author":"H Sun","year":"2023","unstructured":"Sun H, Radicchi F, Kurths J, Bianconi G (2023) The dynamic nature of percolation on networks with triadic interactions. Nat Commun 14(1):1308","journal-title":"Nat Commun"},{"key":"558_CR42","doi-asserted-by":"crossref","unstructured":"Wagner C, Singer P, Karimi F, Pfeffer J, Strohmaier M (2017) Sampling from social networks with attributes. In: Proceedings of the 26th international conference on World Wide Web. WWW \u201917, pp 1181\u20131190, Republic and Canton of Geneva, CHE","DOI":"10.1145\/3038912.3052665"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00558-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-023-00558-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00558-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T04:20:51Z","timestamp":1729657251000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-023-00558-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,27]]},"references-count":42,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["558"],"URL":"https:\/\/doi.org\/10.1007\/s41109-023-00558-3","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2023,6,27]]},"assertion":[{"value":"16 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"39"}}