{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:56:01Z","timestamp":1760234161220,"version":"build-2065373602"},"reference-count":48,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:00:00Z","timestamp":1618876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"The Russian Science Foundation","award":["19-71-00153"],"award-info":[{"award-number":["19-71-00153"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Finding the building blocks of real-world networks contributes to the understanding of their formation process and related dynamical processes, which is related to prediction and control tasks. We explore different types of social networks, demonstrating high structural variability, and aim to extract and see their minimal building blocks, which are able to reproduce supergraph structural and dynamical properties, so as to be appropriate for diffusion prediction for the whole graph on the base of its small subgraph. For this purpose, we determine topological and functional formal criteria and explore sampling techniques. Using the method that provides the best correspondence to both criteria, we explore the building blocks of interest networks. The best sampling method allows one to extract subgraphs of optimal 30 nodes, which reproduce path lengths, clustering, and degree particularities of an initial graph. The extracted subgraphs are different for the considered interest networks, and provide interesting material for the global dynamics exploration on the mesoscale base.<\/jats:p>","DOI":"10.3390\/e23040492","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T13:58:04Z","timestamp":1618927084000},"page":"492","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Subgraphs of Interest Social Networks for Diffusion Dynamics Prediction"],"prefix":"10.3390","volume":"23","author":[{"given":"Valentina Y.","family":"Guleva","sequence":"first","affiliation":[{"name":"National Center for Cognitive Research, ITMO University, 49 Kronverksky Pr., 197101 St. Petersburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Polina O.","family":"Andreeva","sequence":"additional","affiliation":[{"name":"National Center for Cognitive Research, ITMO University, 49 Kronverksky Pr., 197101 St. Petersburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danila A.","family":"Vaganov","sequence":"additional","affiliation":[{"name":"National Center for Cognitive Research, ITMO University, 49 Kronverksky Pr., 197101 St. Petersburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"12755","DOI":"10.1073\/pnas.0903215107","article-title":"Stability of graph communities across time scales","volume":"107","author":"Delvenne","year":"2010","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"30241","DOI":"10.1073\/pnas.2004976117","article-title":"Multiscale structural complexity of natural patterns","volume":"117","author":"Bagrov","year":"2020","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"9843","DOI":"10.1021\/ja011241p","article-title":"Structural characterization of proteins with an attached ATCUN motif by paramagnetic relaxation enhancement NMR spectroscopy","volume":"123","author":"Donaldson","year":"2001","journal-title":"J. Am. Chem. Soc."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Prill, R.J., Iglesias, P.A., and Levchenko, A. (2005). Dynamic properties of network motifs contribute to biological network organization. PLoS Biol., 3.","DOI":"10.1371\/journal.pbio.0030343"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s41060-018-0156-4","article-title":"Motif-aware diffusion network inference","volume":"9","author":"Tan","year":"2020","journal-title":"Int. J. Data Sci. Anal."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/s13278-019-0556-z","article-title":"Using network motifs to characterize temporal network evolution leading to diffusion inhibition","volume":"9","author":"Sarkar","year":"2019","journal-title":"Soc. Netw. Anal. Min."},{"key":"ref_7","unstructured":"Schwarze, A.C., and Porter, M.A. (2020). Motifs for processes on networks. arXiv."},{"key":"ref_8","first-page":"20160216","article-title":"Synchronization patterns: From network motifs to hierarchical networks","volume":"375","author":"Krishnagopal","year":"2017","journal-title":"Philos. Trans. R. Soc. Math. Phys. Eng. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"022915","DOI":"10.1103\/PhysRevE.91.022915","article-title":"Partial synchronization and partial amplitude death in mesoscale network motifs","volume":"91","author":"Poel","year":"2015","journal-title":"Phys. Rev. E"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"28001","DOI":"10.1209\/0295-5075\/78\/28001","article-title":"Synchronization properties of network motifs","volume":"78","author":"Lodato","year":"2007","journal-title":"EPL (Europhys. Lett.)"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"037116","DOI":"10.1063\/1.2953582","article-title":"Synchronization properties of network motifs: Influence of coupling delay and symmetry","volume":"18","author":"Vicente","year":"2008","journal-title":"Chaos Interdiscip. J. Nonlinear Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/j.physa.2004.05.033","article-title":"Fitness for synchronization of network motifs","volume":"343","author":"Vega","year":"2004","journal-title":"Phys. A Stat. Mech. Its Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3173043","article-title":"Rumor spreading and conductance","volume":"65","author":"Chierichetti","year":"2018","journal-title":"J. ACM (JACM)"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","article-title":"Approximating the permanent","volume":"18","author":"Jerrum","year":"1989","journal-title":"SIAM J. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"062312","DOI":"10.1103\/PhysRevE.98.062312","article-title":"Feedback through graph motifs relates structure and function in complex networks","volume":"98","author":"Hu","year":"2018","journal-title":"Phys. Rev. E"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"3093","DOI":"10.1088\/0305-4470\/26\/13\/014","article-title":"Real space renormalization group approach to the random field Ising model","volume":"26","author":"Dayan","year":"1993","journal-title":"J. Phys. A Math. Gen."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1126\/science.aad9029","article-title":"Higher-order organization of complex networks","volume":"353","author":"Benson","year":"2016","journal-title":"Science"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1038\/s41567-018-0072-5","article-title":"Multiscale unfolding of real networks by geometric renormalization","volume":"14","author":"Serrano","year":"2018","journal-title":"Nat. Phys."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/11599128_7","article-title":"Frequency Concepts and Pattern Detection for the Analysis of Motifs in Networks","volume":"3","author":"Schreiber","year":"2005","journal-title":"Trans. Comp. Sys. Biol."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Jazayeri, A., and Yang, C.C. (2020). Motif Discovery Algorithms in Static and Temporal Networks: A Survey. arXiv.","DOI":"10.1093\/comnet\/cnaa031"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s10618-005-0003-9","article-title":"Finding Frequent Patterns in a Large Sparse Graph","volume":"11","author":"Kuramochi","year":"2004","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3572","DOI":"10.1093\/bioinformatics\/bti556","article-title":"MAVisto: A tool for the exploration of network motifs","volume":"21 17","author":"Schreiber","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_23","unstructured":"Schreiber, F., and Schw\u00f6bbermeyer, H. (2004, January 5\u20137). Towards Motif Detection in Networks: Frequency Concepts and Flexible Search. Proceedings of the International Workshop on Network Tools and Applications in Biology NETTAB04, Camerino, Italy."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Kuramochi, M., and Karypis, G. (2004, January 1\u20134). GREW\u2014 A scalable frequent subgraph discovery algorithm. Proceedings of the Fourth IEEE International Conference on Data Mining, ICDM 2004, Brighton, UK.","DOI":"10.21236\/ADA439436"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Elhesha, R., and Kahveci, T. (2016). Identification of large disjoint motifs in biological networks. BMC Bioinform., 17.","DOI":"10.1186\/s12859-016-1271-7"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Dess\u00ec, D., Cirrone, J., Recupero, D.R., and Shasha, D. (2018). SuperNoder: A tool to discover over-represented modular structures in networks. BMC Bioinform., 19.","DOI":"10.1186\/s12859-018-2350-8"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1093\/bioinformatics\/btl038","article-title":"FANMOD: A tool for fast network motif detection","volume":"22","author":"Wernicke","year":"2006","journal-title":"Bioinformatics"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1109\/TCBB.2006.51","article-title":"Efficient detection of network motifs","volume":"3","author":"Wernicke","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.artmed.2007.07.006","article-title":"Bridge and brick network motifs: Identifying significant building blocks from complex biological systems","volume":"41","author":"Huang","year":"2007","journal-title":"Artif. Intell. Med."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Sporns, O., and K\u00f6tter, R. (2004). Motifs in brain networks. PLoS Biol., 2.","DOI":"10.1371\/journal.pbio.0020369"},{"key":"ref_31","first-page":"1","article-title":"Deciphering the global organization of clustering in real complex networks","volume":"3","author":"Serrano","year":"2013","journal-title":"Sci. Rep."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1126\/science.1242063","article-title":"Control profiles of complex networks","volume":"343","author":"Ruths","year":"2014","journal-title":"Science"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41598-017-07209-5","article-title":"Reliable multi-fractal characterization of weighted complex networks: Algorithms and implications","volume":"7","author":"Xue","year":"2017","journal-title":"Sci. Rep."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Zaykov, A.L., Vaganov, D.A., and Guleva, V.Y. (2020). Diffusion Dynamics Prediction on Networks Using Sub-graph Motif Distribution. International Conference on Complex Networks and Their Applications, Springer.","DOI":"10.1007\/978-3-030-65347-7_40"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Brauer, F., Castillo-Chavez, C., and Castillo-Chavez, C. (2012). Mathematical Models in Population Biology and Epidemiology, Springer.","DOI":"10.1007\/978-1-4614-1686-9"},{"key":"ref_36","unstructured":"Prokhorenkova, L., Gusev, G., Vorobev, A., Dorogush, A.V., and Gulin, A. (2019). CatBoost: Unbiased boosting with categorical features. arXiv."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Rozemberczki, B., Kiss, O., and Sarkar, R. (2020, January 19\u201323). Little Ball of Fur: A Python Library for Graph Sampling. Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM\u201920), Galway, Ireland.","DOI":"10.1145\/3340531.3412758"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"4221","DOI":"10.1073\/pnas.0501179102","article-title":"Subnets of scale-free networks are not scale-free: Sampling properties of networks","volume":"102","author":"Stumpf","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Leskovec, J., and Faloutsos, C. (2006, January 20\u201326). Sampling from Large Graphs. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.","DOI":"10.1145\/1150402.1150479"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Boutaba, R., Almeroth, K., Puigjaner, R., Shen, S., and Black, J.P. (2005). Reducing Large Internet Topologies for Faster Simulations. NETWORKING 2005. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems, Springer.","DOI":"10.1007\/b136094"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1214\/aoms\/1177705148","article-title":"Snowball Sampling","volume":"32","author":"Goodman","year":"1961","journal-title":"Ann. Math. Stat."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Maiya, A.S., and Berger-Wolf, T.Y. (2010, January 26\u201330). Sampling Community Structure. Proceedings of the 19th International Conference on World Wide Web, New York, NY, USA.","DOI":"10.1145\/1772690.1772762"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/j.physa.2015.01.030","article-title":"Sampling social networks using shortest paths","volume":"424","author":"Rezvanian","year":"2015","journal-title":"Phys. A Stat. Mech. Its Appl."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Gjoka, M., Kurant, M., Butts, C., and Markopoulou, A. (2010, January 14\u201319). Walking in Facebook: A Case Study of Unbiased Sampling of OSNs. Proceedings of the 2010 Proceedings IEEE INFOCOM, San Diego, CA, USA.","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"H\u00fcbler, C., Kriegel, H.P., Borgwardt, K., and Ghahramani, Z. (2008, January 15\u201319). Metropolis Algorithms for Representative Subgraph Sampling. Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, Pisa, Italy.","DOI":"10.1109\/ICDM.2008.124"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Ribeiro, B., and Towsley, D. (2010). Estimating and Sampling Graphs with Multidimensional Random Walks, Association for Computing Machinery.","DOI":"10.1145\/1879141.1879192"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1145\/2318857.2254795","article-title":"Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling","volume":"40","author":"Lee","year":"2012","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"ref_48","unstructured":"Medvedev, A.N., Lambiotte, R., and Delvenne, J.C. (2017). The Anatomy of Reddit: An Overview of Academic Research, Springer. Dynamics on and of Complex Networks."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/4\/492\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:50:23Z","timestamp":1760161823000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/4\/492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,20]]},"references-count":48,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["e23040492"],"URL":"https:\/\/doi.org\/10.3390\/e23040492","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,4,20]]}}}