1
|
Melo D, Pallares LF, Ayroles JF. Reassessing the modularity of gene co-expression networks using the Stochastic Block Model. PLoS Comput Biol 2024; 20:e1012300. [PMID: 39074140 PMCID: PMC11309492 DOI: 10.1371/journal.pcbi.1012300] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/27/2023] [Revised: 08/08/2024] [Accepted: 07/07/2024] [Indexed: 07/31/2024] Open
Abstract
Finding communities in gene co-expression networks is a common first step toward extracting biological insight from these complex datasets. Most community detection algorithms expect genes to be organized into assortative modules, that is, groups of genes that are more associated with each other than with genes in other groups. While it is reasonable to expect that these modules exist, using methods that assume they exist a priori is risky, as it guarantees that alternative organizations of gene interactions will be ignored. Here, we ask: can we find meaningful communities without imposing a modular organization on gene co-expression networks, and how modular are these communities? For this, we use a recently developed community detection method, the weighted degree corrected stochastic block model (SBM), that does not assume that assortative modules exist. Instead, the SBM attempts to efficiently use all information contained in the co-expression network to separate the genes into hierarchically organized blocks of genes. Using RNAseq gene expression data measured in two tissues derived from an outbred population of Drosophila melanogaster, we show that (a) the SBM is able to find ten times as many groups as competing methods, that (b) several of those gene groups are not modular, and that (c) the functional enrichment for non-modular groups is as strong as for modular communities. These results show that the transcriptome is structured in more complex ways than traditionally thought and that we should revisit the long-standing assumption that modularity is the main driver of the structuring of gene co-expression networks.
Collapse
Affiliation(s)
- Diogo Melo
- Lewis-Sigler Institute for Integrative Genomics, Princeton University, Princeton, New Jersey, United States of America
- Department of Ecology and Evolutionary Biology, Princeton University, Princeton, New Jersey, United States of America
| | - Luisa F. Pallares
- Lewis-Sigler Institute for Integrative Genomics, Princeton University, Princeton, New Jersey, United States of America
- Department of Ecology and Evolutionary Biology, Princeton University, Princeton, New Jersey, United States of America
- Friedrich Miescher Laboratory of the Max Planck Society, Tübingen, Germany
| | - Julien F. Ayroles
- Lewis-Sigler Institute for Integrative Genomics, Princeton University, Princeton, New Jersey, United States of America
- Department of Ecology and Evolutionary Biology, Princeton University, Princeton, New Jersey, United States of America
| |
Collapse
|
2
|
Melo D, Pallares LF, Ayroles JF. Reassessing the modularity of gene co-expression networks using the Stochastic Block Model. BIORXIV : THE PREPRINT SERVER FOR BIOLOGY 2024:2023.05.31.542906. [PMID: 37398186 PMCID: PMC10312592 DOI: 10.1101/2023.05.31.542906] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 07/04/2023]
Abstract
Finding communities in gene co-expression networks is a common first step toward extracting biological insight from these complex datasets. Most community detection algorithms expect genes to be organized into assortative modules, that is, groups of genes that are more associated with each other than with genes in other groups. While it is reasonable to expect that these modules exist, using methods that assume they exist a priori is risky, as it guarantees that alternative organizations of gene interactions will be ignored. Here, we ask: can we find meaningful communities without imposing a modular organization on gene co-expression networks, and how modular are these communities? For this, we use a recently developed community detection method, the weighted degree corrected stochastic block model (SBM), that does not assume that assortative modules exist. Instead, the SBM attempts to efficiently use all information contained in the co-expression network to separate the genes into hierarchically organized blocks of genes. Using RNA-seq gene expression data measured in two tissues derived from an outbred population of Drosophila melanogaster, we show that (a) the SBM is able to find ten times as many groups as competing methods, that (b) several of those gene groups are not modular, and that (c) the functional enrichment for non-modular groups is as strong as for modular communities. These results show that the transcriptome is structured in more complex ways than traditionally thought and that we should revisit the long-standing assumption that modularity is the main driver of the structuring of gene co-expression networks.
Collapse
Affiliation(s)
- Diogo Melo
- Lewis-Sigler Institute for Integrative Genomics, Princeton University, Princeton, NJ, USA
- Department of Ecology and Evolutionary Biology, Princeton University, Princeton, NJ, USA
| | - Luisa F Pallares
- Lewis-Sigler Institute for Integrative Genomics, Princeton University, Princeton, NJ, USA
- Department of Ecology and Evolutionary Biology, Princeton University, Princeton, NJ, USA
- Friedrich Miescher Laboratory of the Max Planck Society, Tübingen, Germany
| | - Julien F Ayroles
- Lewis-Sigler Institute for Integrative Genomics, Princeton University, Princeton, NJ, USA
- Department of Ecology and Evolutionary Biology, Princeton University, Princeton, NJ, USA
| |
Collapse
|
3
|
Brooks SJ, Jones VO, Wang H, Deng C, Golding SGH, Lim J, Gao J, Daoutidis P, Stamoulis C. Community detection in the human connectome: Method types, differences and their impact on inference. Hum Brain Mapp 2024; 45:e26669. [PMID: 38553865 PMCID: PMC10980844 DOI: 10.1002/hbm.26669] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/25/2023] [Revised: 03/06/2024] [Accepted: 03/12/2024] [Indexed: 04/02/2024] Open
Abstract
Community structure is a fundamental topological characteristic of optimally organized brain networks. Currently, there is no clear standard or systematic approach for selecting the most appropriate community detection method. Furthermore, the impact of method choice on the accuracy and robustness of estimated communities (and network modularity), as well as method-dependent relationships between network communities and cognitive and other individual measures, are not well understood. This study analyzed large datasets of real brain networks (estimated from resting-state fMRI fromn $$ n $$ = 5251 pre/early adolescents in the adolescent brain cognitive development [ABCD] study), andn $$ n $$ = 5338 synthetic networks with heterogeneous, data-inspired topologies, with the goal to investigate and compare three classes of community detection methods: (i) modularity maximization-based (Newman and Louvain), (ii) probabilistic (Bayesian inference within the framework of stochastic block modeling (SBM)), and (iii) geometric (based on graph Ricci flow). Extensive comparisons between methods and their individual accuracy (relative to the ground truth in synthetic networks), and reliability (when applied to multiple fMRI runs from the same brains) suggest that the underlying brain network topology plays a critical role in the accuracy, reliability and agreement of community detection methods. Consistent method (dis)similarities, and their correlations with topological properties, were estimated across fMRI runs. Based on synthetic graphs, most methods performed similarly and had comparable high accuracy only in some topological regimes, specifically those corresponding to developed connectomes with at least quasi-optimal community organization. In contrast, in densely and/or weakly connected networks with difficult to detect communities, the methods yielded highly dissimilar results, with Bayesian inference within SBM having significantly higher accuracy compared to all others. Associations between method-specific modularity and demographic, anthropometric, physiological and cognitive parameters showed mostly method invariance but some method dependence as well. Although method sensitivity to different levels of community structure may in part explain method-dependent associations between modularity estimates and parameters of interest, method dependence also highlights potential issues of reliability and reproducibility. These findings suggest that a probabilistic approach, such as Bayesian inference in the framework of SBM, may provide consistently reliable estimates of community structure across network topologies. In addition, to maximize robustness of biological inferences, identified network communities and their cognitive, behavioral and other correlates should be confirmed with multiple reliable detection methods.
Collapse
Affiliation(s)
- Skylar J. Brooks
- Boston Children's HospitalDepartment of PediatricsBostonMassachusettsUSA
- University of California BerkeleyHelen Wills Neuroscience InstituteBerkeleyCaliforniaUSA
| | - Victoria O. Jones
- University of MinnesotaDepartment of Chemical Engineering and Material ScienceMinneapolisMinnesotaUSA
| | - Haotian Wang
- Rutgers UniversityDepartment of Computer SciencePiscatawayNew JerseyUSA
| | - Chengyuan Deng
- Rutgers UniversityDepartment of Computer SciencePiscatawayNew JerseyUSA
| | | | - Jethro Lim
- Boston Children's HospitalDepartment of PediatricsBostonMassachusettsUSA
| | - Jie Gao
- Rutgers UniversityDepartment of Computer SciencePiscatawayNew JerseyUSA
| | - Prodromos Daoutidis
- University of MinnesotaDepartment of Chemical Engineering and Material ScienceMinneapolisMinnesotaUSA
| | - Catherine Stamoulis
- Boston Children's HospitalDepartment of PediatricsBostonMassachusettsUSA
- Harvard Medical SchoolDepartment of PediatricsBostonMassachusettsUSA
| |
Collapse
|
4
|
Su X, Xue S, Liu F, Wu J, Yang J, Zhou C, Hu W, Paris C, Nepal S, Jin D, Sheng QZ, Yu PS. A Comprehensive Survey on Community Detection With Deep Learning. IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024; 35:4682-4702. [PMID: 35263257 DOI: 10.1109/tnnls.2021.3137396] [Citation(s) in RCA: 27] [Impact Index Per Article: 27.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/14/2023]
Abstract
Detecting a community in a network is a matter of discerning the distinct features and connections of a group of members that are different from those in other communities. The ability to do this is of great significance in network analysis. However, beyond the classic spectral clustering and statistical inference methods, there have been significant developments with deep learning techniques for community detection in recent years-particularly when it comes to handling high-dimensional network data. Hence, a comprehensive review of the latest progress in community detection through deep learning is timely. To frame the survey, we have devised a new taxonomy covering different state-of-the-art methods, including deep learning models based on deep neural networks (DNNs), deep nonnegative matrix factorization, and deep sparse filtering. The main category, i.e., DNNs, is further divided into convolutional networks, graph attention networks, generative adversarial networks, and autoencoders. The popular benchmark datasets, evaluation metrics, and open-source implementations to address experimentation settings are also summarized. This is followed by a discussion on the practical applications of community detection in various domains. The survey concludes with suggestions of challenging topics that would make for fruitful future research directions in this fast-growing deep learning field.
Collapse
|
5
|
Kritschgau J, Kaiser D, Alvarado Rodriguez O, Amburg I, Bolkema J, Grubb T, Lan F, Maleki S, Chodrow P, Kay B. Community detection in hypergraphs via mutual information maximization. Sci Rep 2024; 14:6933. [PMID: 38521798 PMCID: PMC10960844 DOI: 10.1038/s41598-024-55934-5] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/08/2023] [Accepted: 02/29/2024] [Indexed: 03/25/2024] Open
Abstract
The hypergraph community detection problem seeks to identify groups of related vertices in hypergraph data. We propose an information-theoretic hypergraph community detection algorithm which compresses the observed data in terms of community labels and community-edge intersections. This algorithm can also be viewed as maximum-likelihood inference in a degree-corrected microcanonical stochastic blockmodel. We perform the compression/inference step via simulated annealing. Unlike several recent algorithms based on canonical models, our microcanonical algorithm does not require inference of statistical parameters such as vertex degrees or pairwise group connection rates. Through synthetic experiments, we find that our algorithm succeeds down to recently-conjectured thresholds for sparse random hypergraphs. We also find competitive performance in cluster recovery tasks on several hypergraph data sets.
Collapse
Affiliation(s)
- Jürgen Kritschgau
- Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, 15213, USA
| | - Daniel Kaiser
- Department of Informatics, Indiana University, Bloomington, IN, 47408, USA
| | | | - Ilya Amburg
- Pacific Northwest National Laboratory, Richland, WA, 99354, USA
| | - Jessalyn Bolkema
- Department of Mathematics, California State University, Dominguez Hills, Carson, CA, 90747, USA
| | - Thomas Grubb
- University of California San Diego, San Diego, CA, 92093, USA
| | - Fangfei Lan
- Scientific Computing and Imaging Institute, University of Utah, Salt Lake City, UT, 84112, USA
| | - Sepideh Maleki
- Department of Computer Science, University of Texas at Austin, Austin, TX, 78712, USA
| | - Phil Chodrow
- Department of Computer Science, Middlebury College, Middlebury, VT, 05753, USA
| | - Bill Kay
- Pacific Northwest National Laboratory, Richland, WA, 99354, USA.
| |
Collapse
|
6
|
Ruggeri N, Battiston F, De Bacco C. Framework to generate hypergraphs with community structure. Phys Rev E 2024; 109:034309. [PMID: 38632750 DOI: 10.1103/physreve.109.034309] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/23/2022] [Accepted: 01/11/2024] [Indexed: 04/19/2024]
Abstract
In recent years hypergraphs have emerged as a powerful tool to study systems with multibody interactions which cannot be trivially reduced to pairs. While highly structured methods to generate synthetic data have proved fundamental for the standardized evaluation of algorithms and the statistical study of real-world networked data, these are scarcely available in the context of hypergraphs. Here we propose a flexible and efficient framework for the generation of hypergraphs with many nodes and large hyperedges, which allows specifying general community structures and tune different local statistics. We illustrate how to use our model to sample synthetic data with desired features (assortative or disassortative communities, mixed or hard community assignments, etc.), analyze community detection algorithms, and generate hypergraphs structurally similar to real-world data. Overcoming previous limitations on the generation of synthetic hypergraphs, our work constitutes a substantial advancement in the statistical modeling of higher-order systems.
Collapse
Affiliation(s)
- Nicolò Ruggeri
- Max Planck Institute for Intelligent Systems, Cyber Valley, 72076 Tübingen, Germany
- Department of Computer Science, ETH, 8004 Zürich, Switzerland
| | - Federico Battiston
- Department of Network and Data Science, Central European University, 1100 Vienna, Austria
| | - Caterina De Bacco
- Max Planck Institute for Intelligent Systems, Cyber Valley, 72076 Tübingen, Germany
| |
Collapse
|
7
|
Goldstone RL, Dubova M, Aiyappa R, Edinger A. The Spread of Beliefs in Partially Modularized Communities. PERSPECTIVES ON PSYCHOLOGICAL SCIENCE 2024; 19:404-417. [PMID: 38019565 DOI: 10.1177/17456916231198238] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/30/2023]
Abstract
Many life-influencing social networks are characterized by considerable informational isolation. People within a community are far more likely to share beliefs than people who are part of different communities. The spread of useful information across communities is impeded by echo chambers (far greater connectivity within than between communities) and filter bubbles (more influence of beliefs by connected neighbors within than between communities). We apply the tools of network analysis to organize our understanding of the spread of beliefs across modularized communities and to predict the effect of individual and group parameters on the dynamics and distribution of beliefs. In our Spread of Beliefs in Modularized Communities (SBMC) framework, a stochastic block model generates social networks with variable degrees of modularity, beliefs have different observable utilities, individuals change their beliefs on the basis of summed or average evidence (or intermediate decision rules), and parameterized stochasticity introduces randomness into decisions. SBMC simulations show surprising patterns; for example, increasing out-group connectivity does not always improve group performance, adding randomness to decisions can promote performance, and decision rules that sum rather than average evidence can improve group performance, as measured by the average utility of beliefs that the agents adopt. Overall, the results suggest that intermediate degrees of belief exploration are beneficial for the spread of useful beliefs in a community, and so parameters that pull in opposite directions on an explore-exploit continuum are usefully paired.
Collapse
Affiliation(s)
- Robert L Goldstone
- Department of Psychological and Brain Sciences, Indiana University
- Program in Cognitive Science, Indiana University
| | | | - Rachith Aiyappa
- Center for Complex Networks and Systems, Luddy School of Informatics, Computing, and Engineering, Indiana University
| | - Andy Edinger
- Program in Cognitive Science, Indiana University
- Center for Complex Networks and Systems, Luddy School of Informatics, Computing, and Engineering, Indiana University
| |
Collapse
|
8
|
Kirkley A. Identifying hubs in directed networks. Phys Rev E 2024; 109:034310. [PMID: 38632822 DOI: 10.1103/physreve.109.034310] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/13/2023] [Accepted: 02/06/2024] [Indexed: 04/19/2024]
Abstract
Nodes in networks that exhibit high connectivity, also called "hubs," play a critical role in determining the structural and functional properties of networked systems. However, there is no clear definition of what constitutes a hub node in a network, and the classification of network hubs in existing work has either been purely qualitative or relies on ad hoc criteria for thresholding continuous data that do not generalize well to networks with certain degree sequences. Here we develop a set of efficient nonparametric methods that classify hub nodes in directed networks using the Minimum Description Length principle, effectively providing a clear and principled definition for network hubs. We adapt our methods to both unweighted and weighted networks, and we demonstrate them in a range of example applications using real and synthetic network data.
Collapse
Affiliation(s)
- Alec Kirkley
- Institute of Data Science, University of Hong Kong, Hong Kong, China; Department of Urban Planning and Design, University of Hong Kong, Hong Kong, China; and Urban Systems Institute, University of Hong Kong, Hong Kong, China
| |
Collapse
|
9
|
Gaüzère P, Botella C, Poggiato G, O'Connor L, Di Marco M, Dragonetti C, Maiorano L, Renaud J, Thuiller W. Dissimilarity of vertebrate trophic interactions reveals spatial uniqueness but functional redundancy across Europe. Curr Biol 2023; 33:5263-5271.e3. [PMID: 37992717 DOI: 10.1016/j.cub.2023.10.069] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/29/2023] [Revised: 10/24/2023] [Accepted: 10/30/2023] [Indexed: 11/24/2023]
Abstract
Identifying areas that contain species assemblages not found elsewhere in a region is central to conservation planning.1,2 Species assemblages contain networks of species interactions that underpin species dynamics,3,4 ecosystem processes, and contributions to people.5,6,7 Yet the uniqueness of interaction networks in a regional context has rarely been assessed. Here, we estimated the spatial uniqueness of 10,000 terrestrial vertebrate trophic networks across Europe (1,164 species, 50,408 potential interactions8) based on the amount of similarity between all local networks mapped at a 10 km resolution. Our results revealed more unique networks in the Arctic bioregion, but also in southern Europe and isolated islands. We then contrasted the uniqueness of trophic networks with their vulnerability to human footprint and future climate change and measured their coverage within protected areas. This analysis revealed that unique networks situated in southern Europe were particularly exposed to human footprint and that unique networks in the Arctic might be at risk from future climate change. However, considering interaction networks at the level of trophic groups, rather than species, revealed that the general structure of trophic networks was redundant across the continent, in contrast to species' interactions. We argue that proactive European conservation strategies might gain relevance by turning their eyes toward interaction networks that are both unique and vulnerable.
Collapse
Affiliation(s)
- Pierre Gaüzère
- University of Grenoble Alpes, University of Savoie Mont Blanc, CNRS, LECA, 38000 Grenoble, France.
| | | | - Giovanni Poggiato
- University of Grenoble Alpes, University of Savoie Mont Blanc, CNRS, LECA, 38000 Grenoble, France
| | - Louise O'Connor
- University of Grenoble Alpes, University of Savoie Mont Blanc, CNRS, LECA, 38000 Grenoble, France; Biodiversity, Ecology and Conservation Group, International Institute for Applied Systems Analysis (IIASA), Schlossplatz 1, 2361 Laxenburg, Austria
| | - Moreno Di Marco
- Department of Biology and Biotechnologies "Charles Darwin," "Sapienza," University of Rome, 00185 Roma, Italy
| | - Chiara Dragonetti
- Department of Biology and Biotechnologies "Charles Darwin," "Sapienza," University of Rome, 00185 Roma, Italy
| | - Luigi Maiorano
- Department of Biology and Biotechnologies "Charles Darwin," "Sapienza," University of Rome, 00185 Roma, Italy
| | - Julien Renaud
- University of Grenoble Alpes, University of Savoie Mont Blanc, CNRS, LECA, 38000 Grenoble, France
| | - Wilfried Thuiller
- University of Grenoble Alpes, University of Savoie Mont Blanc, CNRS, LECA, 38000 Grenoble, France
| |
Collapse
|
10
|
Chen Y, Ye W, Li D. Spectral Clustering Community Detection Algorithm Based on Point-Wise Mutual Information Graph Kernel. ENTROPY (BASEL, SWITZERLAND) 2023; 25:1617. [PMID: 38136497 PMCID: PMC10742989 DOI: 10.3390/e25121617] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/22/2023] [Revised: 11/23/2023] [Accepted: 12/01/2023] [Indexed: 12/24/2023]
Abstract
To address the problem that traditional spectral clustering algorithms cannot obtain the complete structural information of networks, this paper proposes a spectral clustering community detection algorithm, PMIK-SC, based on the point-wise mutual information (PMI) graph kernel. The kernel is constructed according to the point-wise mutual information between nodes, which is then used as a proximity matrix to reconstruct the network and obtain the symmetric normalized Laplacian matrix. Finally, the network is partitioned by the eigendecomposition and eigenvector clustering of the Laplacian matrix. In addition, to determine the number of clusters during spectral clustering, this paper proposes a fast algorithm, BI-CNE, for estimating the number of communities. For a specific network, the algorithm first reconstructs the original network and then runs Monte Carlo sampling to estimate the number of communities by Bayesian inference. Experimental results show that the detection speed and accuracy of the algorithm are superior to other existing algorithms for estimating the number of communities. On this basis, the spectral clustering community detection algorithm PMIK-SC also has high accuracy and stability compared with other community detection algorithms and spectral clustering algorithms.
Collapse
Affiliation(s)
- Yinan Chen
- Department of Computer Science and Technology, Shantou University, Shantou 515821, China
| | - Wenbin Ye
- School of Software Engineering, South China University of Technology, Guangzhou 510006, China; (W.Y.); (D.L.)
| | - Dong Li
- School of Software Engineering, South China University of Technology, Guangzhou 510006, China; (W.Y.); (D.L.)
| |
Collapse
|
11
|
Karimi F, Oliveira M. On the inadequacy of nominal assortativity for assessing homophily in networks. Sci Rep 2023; 13:21053. [PMID: 38030623 PMCID: PMC10686992 DOI: 10.1038/s41598-023-48113-5] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/10/2023] [Accepted: 11/22/2023] [Indexed: 12/01/2023] Open
Abstract
Nominal assortativity (or discrete assortativity) is widely used to characterize group mixing patterns and homophily in networks, enabling researchers to analyze how groups interact with one another. Here we demonstrate that the measure presents severe shortcomings when applied to networks with unequal group sizes and asymmetric mixing. We characterize these shortcomings analytically and use synthetic and empirical networks to show that nominal assortativity fails to account for group imbalance and asymmetric group interactions, thereby producing an inaccurate characterization of mixing patterns. We propose the adjusted nominal assortativity and show that this adjustment recovers the expected assortativity in networks with various level of mixing. Furthermore, we propose an analytical method to assess asymmetric mixing by estimating the tendency of inter- and intra-group connectivities. Finally, we discuss how this approach enables uncovering hidden mixing patterns in real-world networks.
Collapse
Affiliation(s)
- Fariba Karimi
- Complexity Science Hub Vienna, 1080, Vienna, Austria.
- Graz University of Technology, Graz, Austria.
| | | |
Collapse
|
12
|
Liu CX, Alexander TJ, Altmann EG. Nonassortative relationships between groups of nodes are typical in complex networks. PNAS NEXUS 2023; 2:pgad364. [PMID: 38034095 PMCID: PMC10681970 DOI: 10.1093/pnasnexus/pgad364] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 05/16/2023] [Accepted: 10/17/2023] [Indexed: 12/02/2023]
Abstract
Decomposing a graph into groups of nodes that share similar connectivity properties is essential to understand the organization and function of complex networks. Previous works have focused on groups with specific relationships between group members, such as assortative communities or core-periphery structures, developing computational methods to find these mesoscale structures within a network. Here, we go beyond these two traditional cases and introduce a methodology that is able to identify and systematically classify all possible community types in directed multi graphs, based on the pairwise relationship between groups. We apply our approach to 53 different networks and find that assortative communities are the most common structures, but that previously unexplored types appear in almost every network. A particularly prevalent new type of relationship, which we call a source-basin structure, has information flowing from a sparsely connected group of nodes (source) to a densely connected group (basin). We look in detail at two online social networks-a new network of Twitter users and a well-studied network of political blogs-and find that source-basin structures play an important role in both of them. This confirms not only the widespread appearance of nonassortative structures but also the potential of hitherto unidentified relationships to explain the organization of complex networks.
Collapse
Affiliation(s)
- Cathy Xuanchi Liu
- School of Mathematics and Statistics, University of Sydney, Sydney, 2006 NSW, Australia
- Centre for Complex Systems, University of Sydney, Sydney, 2006 NSW, Australia
| | - Tristram J Alexander
- Centre for Complex Systems, University of Sydney, Sydney, 2006 NSW, Australia
- School of Physics, University of Sydney, Sydney, 2006 NSW, Australia
| | - Eduardo G Altmann
- School of Mathematics and Statistics, University of Sydney, Sydney, 2006 NSW, Australia
- Centre for Complex Systems, University of Sydney, Sydney, 2006 NSW, Australia
| |
Collapse
|
13
|
Mangold L, Roth C. Generative models for two-ground-truth partitions in networks. Phys Rev E 2023; 108:054308. [PMID: 38115519 DOI: 10.1103/physreve.108.054308] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/08/2023] [Accepted: 10/09/2023] [Indexed: 12/21/2023]
Abstract
A myriad of approaches have been proposed to characterize the mesoscale structure of networks most often as a partition based on patterns variously called communities, blocks, or clusters. Clearly, distinct methods designed to detect different types of patterns may provide a variety of answers' to the networks mesoscale structure. Yet even multiple runs of a given method can sometimes yield diverse and conflicting results, producing entire landscapes of partitions which potentially include multiple (locally optimal) mesoscale explanations of the network. Such ambiguity motivates a closer look at the ability of these methods to find multiple qualitatively different "ground truth" partitions in a network. Here we propose the stochastic cross-block model (SCBM), a generative model which allows for two distinct partitions to be built into the mesoscale structure of a single benchmark network. We demonstrate a use case of the benchmark model by appraising the power of stochastic block models (SBMs) to detect implicitly planted coexisting bicommunity and core-periphery structures of different strengths. Given our model design and experimental setup, we find that the ability to detect the two partitions individually varies by SBM variant and that coexistence of both partitions is recovered only in a very limited number of cases. Our findings suggest that in most instances only one-in some way dominating-structure can be detected, even in the presence of other partitions. They underline the need for considering entire landscapes of partitions when different competing explanations exist and motivate future research to advance partition coexistence detection methods. Our model also contributes to the field of benchmark networks more generally by enabling further exploration of the ability of new and existing methods to detect ambiguity in the mesoscale structure of networks.
Collapse
Affiliation(s)
- Lena Mangold
- Computational Social Science Team, Centre Marc Bloch, Friedrichstr. 191, 10117 Berlin, Germany
- Centre national de la recherche scientifique (CNRS), 3 rue Michel-Ange, 75 016 Paris, France; and Centre d'Analyse et de Mathématique Sociales (CAMS), École des hautes études en sciences sociales (EHESS), 54 Bd Raspail, 75006 Paris, France
| | - Camille Roth
- Computational Social Science Team, Centre Marc Bloch, Friedrichstr. 191, 10117 Berlin, Germany
- Centre national de la recherche scientifique (CNRS), 3 rue Michel-Ange, 75 016 Paris, France; and Centre d'Analyse et de Mathématique Sociales (CAMS), École des hautes études en sciences sociales (EHESS), 54 Bd Raspail, 75006 Paris, France
| |
Collapse
|
14
|
Musciotto F, Miccichè S. Exploring the landscape of dismantling strategies based on the community structure of networks. Sci Rep 2023; 13:14448. [PMID: 37660149 PMCID: PMC10475058 DOI: 10.1038/s41598-023-40867-2] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/26/2023] [Accepted: 08/17/2023] [Indexed: 09/04/2023] Open
Abstract
Network dismantling is a relevant research area in network science, gathering attention both from a theoretical and an operational point of view. Here, we propose a general framework for dismantling that prioritizes the removal of nodes that bridge together different network communities. The strategies we detect are not unique, as they depend on the specific realization of the community detection algorithm considered. However, when applying the methodology to some synthetic benchmark and real-world networks we find that the dismantling performances are strongly robust, and do not depend on the specific algorithm. Thus, the stochasticity inherently present in many community detection algorithms allows to identify several strategies that have comparable effectiveness but require the removal of distinct subsets of nodes. This feature is highly relevant in operational contexts in which the removal of nodes is costly and allows to identify the least expensive strategy that still holds high effectiveness.
Collapse
Affiliation(s)
- F Musciotto
- Dipartimento di Fisica e Chimica-Emilio Segrè, Università degli Studi di Palermo, Viale delle Scienze, Ed. 18, 90128, Palermo, Italy.
| | - S Miccichè
- Dipartimento di Fisica e Chimica-Emilio Segrè, Università degli Studi di Palermo, Viale delle Scienze, Ed. 18, 90128, Palermo, Italy
| |
Collapse
|
15
|
Atandoh PH, Lee KH. Statistical clustering of documents via stochastic blockmodels. J Appl Stat 2023; 51:1878-1893. [PMID: 39071253 PMCID: PMC11271127 DOI: 10.1080/02664763.2023.2247617] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/31/2022] [Accepted: 07/23/2023] [Indexed: 07/30/2024]
Abstract
As the online market grows rapidly, people are relying more on product review when they purchase the product. Hence, many companies and researchers are interested in analyzing product review which essentially a text data. In the current literature, it is common to use only text analysis tools to analyze text dataset. But in our work, we propose a method that utilizes both text analysis method such as topic modeling and statistical network model to build network among individuals and find interesting communities. We introduce a promising framework that incorporates topic modeling technique to define the edges among the individuals and form a network and uses stochastic blockmodels (SBM) to find the communities. The power of our proposed method is demonstrated in real-world application to Amazon product review dataset.
Collapse
Affiliation(s)
- Paul H. Atandoh
- Department of Mathematics, Mercer University, Macon, GA, USA
| | - Kevin H. Lee
- Department of Statistics, Western Michigan University, Kalamazoo, MI, USA
| |
Collapse
|
16
|
Ren M, Zhang S, Wang J. Consistent estimation of the number of communities via regularized network embedding. Biometrics 2023; 79:2404-2416. [PMID: 36573805 DOI: 10.1111/biom.13815] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/07/2022] [Accepted: 12/20/2022] [Indexed: 12/28/2022]
Abstract
The network analysis plays an important role in numerous application domains including biomedicine. Estimation of the number of communities is a fundamental and critical issue in network analysis. Most existing studies assume that the number of communities is known a priori, or lack of rigorous theoretical guarantee on the estimation consistency. In this paper, we propose a regularized network embedding model to simultaneously estimate the community structure and the number of communities in a unified formulation. The proposed model equips network embedding with a novel composite regularization term, which pushes the embedding vector toward its center and pushes similar community centers collapsed with each other. A rigorous theoretical analysis is conducted, establishing asymptotic consistency in terms of community detection and estimation of the number of communities. Extensive numerical experiments have also been conducted on both synthetic networks and brain functional connectivity network, which demonstrate the superior performance of the proposed method compared with existing alternatives.
Collapse
Affiliation(s)
- Mingyang Ren
- Department of Statistics, The Chinese University of Hong Kong, Ma Liu Shui, Hong Kong
- School of Mathematical Sciences, Key Laboratory of Big Data Mining and Knowledge Management, University of Chinese Academy of Sciences, Beijing, China
| | - Sanguo Zhang
- School of Mathematical Sciences, Key Laboratory of Big Data Mining and Knowledge Management, University of Chinese Academy of Sciences, Beijing, China
| | - Junhui Wang
- Department of Statistics, The Chinese University of Hong Kong, Ma Liu Shui, Hong Kong
| |
Collapse
|
17
|
Dichio V, De Vico Fallani F. Statistical models of complex brain networks: a maximum entropy approach. REPORTS ON PROGRESS IN PHYSICS. PHYSICAL SOCIETY (GREAT BRITAIN) 2023; 86:102601. [PMID: 37437559 DOI: 10.1088/1361-6633/ace6bc] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/10/2022] [Accepted: 07/12/2023] [Indexed: 07/14/2023]
Abstract
The brain is a highly complex system. Most of such complexity stems from the intermingled connections between its parts, which give rise to rich dynamics and to the emergence of high-level cognitive functions. Disentangling the underlying network structure is crucial to understand the brain functioning under both healthy and pathological conditions. Yet, analyzing brain networks is challenging, in part because their structure represents only one possible realization of a generative stochastic process which is in general unknown. Having a formal way to cope with such intrinsic variability is therefore central for the characterization of brain network properties. Addressing this issue entails the development of appropriate tools mostly adapted from network science and statistics. Here, we focus on a particular class of maximum entropy models for networks, i.e. exponential random graph models, as a parsimonious approach to identify the local connection mechanisms behind observed global network structure. Efforts are reviewed on the quest for basic organizational properties of human brain networks, as well as on the identification of predictive biomarkers of neurological diseases such as stroke. We conclude with a discussion on how emerging results and tools from statistical graph modeling, associated with forthcoming improvements in experimental data acquisition, could lead to a finer probabilistic description of complex systems in network neuroscience.
Collapse
Affiliation(s)
- Vito Dichio
- Sorbonne Universite, Paris Brain Institute-ICM, CNRS, Inria, Inserm, AP-HP, Hopital de la Pitie Salpêtriere, F-75013 Paris, France
| | - Fabrizio De Vico Fallani
- Sorbonne Universite, Paris Brain Institute-ICM, CNRS, Inria, Inserm, AP-HP, Hopital de la Pitie Salpêtriere, F-75013 Paris, France
| |
Collapse
|
18
|
Polanco A, Newman MEJ. Hierarchical core-periphery structure in networks. Phys Rev E 2023; 108:024311. [PMID: 37723783 DOI: 10.1103/physreve.108.024311] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/08/2023] [Accepted: 07/23/2023] [Indexed: 09/20/2023]
Abstract
We study core-periphery structure in networks using inference methods based on a flexible network model that allows for traditional onionlike cores within cores, but also for hierarchical treelike structures and more general non-nested types of structures. We propose an efficient Monte Carlo scheme for fitting the model to observed networks and report results for a selection of real-world data sets. Among other things, we observe an empirical distinction between networks showing traditional core-periphery structure with a dense core weakly connected to a sparse periphery, and an alternative structure in which the core is strongly connected both within itself and to the periphery. Networks vary in whether they are better represented by one type of structure or the other. We also observe structures that are a hybrid between core-periphery structure and community structure, in which networks have a set of nonoverlapping cores that roughly correspond to communities, surrounded by a single undifferentiated periphery. Computer code implementing our methods is available.
Collapse
Affiliation(s)
- Austin Polanco
- Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA
| | - M E J Newman
- Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA
- Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA
| |
Collapse
|
19
|
Peixoto TP, Kirkley A. Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection. Phys Rev E 2023; 108:024309. [PMID: 37723811 DOI: 10.1103/physreve.108.024309] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/24/2022] [Accepted: 08/02/2023] [Indexed: 09/20/2023]
Abstract
The task of community detection, which aims to partition a network into clusters of nodes to summarize its large-scale structure, has spawned the development of many competing algorithms with varying objectives. Some community detection methods are inferential, explicitly deriving the clustering objective through a probabilistic generative model, while other methods are descriptive, dividing a network according to an objective motivated by a particular application, making it challenging to compare these methods on the same scale. Here we present a solution to this problem that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model. This allows us to compute the description length of a network and its partition under arbitrary objectives, providing a principled measure to compare the performance of different algorithms without the need for "ground-truth" labels. Our approach also gives access to instances of the community detection problem that are optimal to any given algorithm and in this way reveals intrinsic biases in popular descriptive methods, explaining their tendency to overfit. Using our framework, we compare a number of community detection methods on artificial networks and on a corpus of over 500 structurally diverse empirical networks. We find that more expressive community detection methods exhibit consistently superior compression performance on structured data instances, without having degraded performance on a minority of situations where more specialized algorithms perform optimally. Our results undermine the implications of the "no free lunch" theorem for community detection, both conceptually and in practice, since it is confined to unstructured data instances, unlike relevant community detection problems which are structured by requirement.
Collapse
Affiliation(s)
- Tiago P Peixoto
- Department of Network and Data Science, Central European University, 1100 Vienna, Austria
| | - Alec Kirkley
- Institute of Data Science, University of Hong Kong, Hong Kong; Department of Urban Planning and Design, University of Hong Kong, Hong Kong; and Urban Systems Institute, University of Hong Kong, Hong Kong
| |
Collapse
|
20
|
Ochi M, Kawamoto T. Finding community structure using the ordered random graph model. Phys Rev E 2023; 108:014303. [PMID: 37583142 DOI: 10.1103/physreve.108.014303] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/17/2022] [Accepted: 06/07/2023] [Indexed: 08/17/2023]
Abstract
Visualization of the adjacency matrix enables us to capture macroscopic features of a network when the matrix elements are aligned properly. Community structure, a network consisting of several densely connected components, is a particularly important feature and the structure can be identified through the adjacency matrix when it is close to a block-diagonal form. However, classical ordering algorithms for matrices fail to align matrix elements such that the community structure is visible. In this study, we propose an ordering algorithm based on the maximum-likelihood estimate of the ordered random graph model. We show that the proposed method allows us to more clearly identify community structures than the existing ordering algorithms.
Collapse
Affiliation(s)
- Masaki Ochi
- Department of Physics, The University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8574, Japan
| | - Tatsuro Kawamoto
- Artificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology, 2-3-26 Aomi, Koto-ku, Tokyo 135-0064, Japan
| |
Collapse
|
21
|
Yang R, Vishwanathan A, Wu J, Kemnitz N, Ih D, Turner N, Lee K, Tartavull I, Silversmith WM, Jordan CS, David C, Bland D, Sterling A, Goldman MS, Aksay ERF, Seung HS. Cyclic structure with cellular precision in a vertebrate sensorimotor neural circuit. Curr Biol 2023; 33:2340-2349.e3. [PMID: 37236180 PMCID: PMC10419332 DOI: 10.1016/j.cub.2023.05.010] [Citation(s) in RCA: 2] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/07/2022] [Revised: 01/24/2023] [Accepted: 05/05/2023] [Indexed: 05/28/2023]
Abstract
Neuronal wiring diagrams reconstructed by electron microscopy1,2,3,4,5 pose new questions about the organization of nervous systems following the time-honored tradition of cross-species comparisons.6,7 The C. elegans connectome has been conceptualized as a sensorimotor circuit that is approximately feedforward,8,9,10,11 starting from sensory neurons proceeding to interneurons and ending with motor neurons. Overrepresentation of a 3-cell motif often known as the "feedforward loop" has provided further evidence for feedforwardness.10,12 Here, we contrast with another sensorimotor wiring diagram that was recently reconstructed from a larval zebrafish brainstem.13 We show that the 3-cycle, another 3-cell motif, is highly overrepresented in the oculomotor module of this wiring diagram. This is a first for any neuronal wiring diagram reconstructed by electron microscopy, whether invertebrate12,14 or mammalian.15,16,17 The 3-cycle of cells is "aligned" with a 3-cycle of neuronal groups in a stochastic block model (SBM)18 of the oculomotor module. However, the cellular cycles exhibit more specificity than can be explained by the group cycles-recurrence to the same neuron is surprisingly common. Cyclic structure could be relevant for theories of oculomotor function that depend on recurrent connectivity. The cyclic structure coexists with the classic vestibulo-ocular reflex arc for horizontal eye movements,19 and could be relevant for recurrent network models of temporal integration by the oculomotor system.20,21.
Collapse
Affiliation(s)
- Runzhe Yang
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA; Computer Science Department, Princeton University, Princeton, NJ 08540, USA
| | - Ashwin Vishwanathan
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | - Jingpeng Wu
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | - Nico Kemnitz
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | - Dodam Ih
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | - Nicholas Turner
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA; Computer Science Department, Princeton University, Princeton, NJ 08540, USA
| | - Kisuk Lee
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA; Brain & Cognitive Sciences Department, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
| | - Ignacio Tartavull
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | | | - Chris S Jordan
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | - Celia David
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | - Doug Bland
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | - Amy Sterling
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA
| | - Mark S Goldman
- Center for Neuroscience, Department of Neurobiology, Physiology, and Behavior, and Department of Ophthalmology and Vision Science, University of California, Davis, Davis, CA 95616, USA
| | - Emre R F Aksay
- Institute for Computational Biomedicine and Department of Physiology and Biophysics, Weill Cornell Medical College, New York, NY 10021, USA
| | - H Sebastian Seung
- Princeton Neuroscience Institute, Princeton University, Princeton, NJ 08540, USA; Computer Science Department, Princeton University, Princeton, NJ 08540, USA.
| |
Collapse
|
22
|
Karaaslanli A, Ortiz-Bouza M, Munia TTK, Aviyente S. Community detection in multi-frequency EEG networks. Sci Rep 2023; 13:8114. [PMID: 37208422 DOI: 10.1038/s41598-023-35232-2] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/29/2022] [Accepted: 05/15/2023] [Indexed: 05/21/2023] Open
Abstract
Functional connectivity networks of the human brain are commonly studied using tools from complex network theory. Existing methods focus on functional connectivity within a single frequency band. However, it is well-known that higher order brain functions rely on the integration of information across oscillations at different frequencies. Therefore, there is a need to study these cross-frequency interactions. In this paper, we use multilayer networks to model functional connectivity across multiple frequencies, where each layer corresponds to a different frequency band. We then introduce the multilayer modularity metric to develop a multilayer community detection algorithm. The proposed approach is applied to electroencephalogram (EEG) data collected during a study of error monitoring in the human brain. The differences between the community structures within and across different frequency bands for two response types, i.e. error and correct, are studied. The results indicate that following an error response, the brain organizes itself to form communities across frequencies, in particular between theta and gamma bands while a similar cross-frequency community formation is not observed following the correct response.
Collapse
Affiliation(s)
- Abdullah Karaaslanli
- Department of Electrical and Computer Engineering, Michigan State University, East Lansing, MI, 48824, USA.
| | - Meiby Ortiz-Bouza
- Department of Electrical and Computer Engineering, Michigan State University, East Lansing, MI, 48824, USA
| | - Tamanna T K Munia
- Department of Electrical and Computer Engineering, Michigan State University, East Lansing, MI, 48824, USA
| | - Selin Aviyente
- Department of Electrical and Computer Engineering, Michigan State University, East Lansing, MI, 48824, USA
| |
Collapse
|
23
|
Bobak CA, Zhao Y, Levy JJ, O’Malley AJ. GRANDPA: GeneRAtive network sampling using degree and property augmentation applied to the analysis of partially confidential healthcare networks. APPLIED NETWORK SCIENCE 2023; 8:23. [PMID: 37188323 PMCID: PMC10173245 DOI: 10.1007/s41109-023-00548-5] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 12/01/2022] [Accepted: 04/24/2023] [Indexed: 05/17/2023]
Abstract
Protecting medical privacy can create obstacles in the analysis and distribution of healthcare graphs and statistical inferences accompanying them. We pose a graph simulation model which generates networks using degree and property augmentation and provide a flexible R package that allows users to create graphs that preserve vertex attribute relationships and approximating the retention of topological properties observed in the original graph (e.g., community structure). We illustrate our proposed algorithm using a case study based on Zachary's karate network and a patient-sharing graph generated from Medicare claims data in 2019. In both cases, we find that community structure is preserved, and normalized root mean square error between cumulative distributions of the degrees across the generated and the original graphs is low (0.0508 and 0.0514 respectively).
Collapse
Affiliation(s)
- Carly A. Bobak
- Department of Biomedical Data Science, Dartmouth College, Hanover, NH USA
- The Dartmouth Institute for Health Policy and Clinical Practice, Dartmouth College, Hanover, NH USA
- Research Computing, Dartmouth College, Hanover, NH USA
| | - Yifan Zhao
- Department of Biomedical Data Science, Dartmouth College, Hanover, NH USA
- The Dartmouth Institute for Health Policy and Clinical Practice, Dartmouth College, Hanover, NH USA
| | - Joshua J. Levy
- Department of Pathology and Laboratory Medicine, Dartmouth College, Hanover, NH USA
- Department of Dermatology, Dartmouth College, Hanover, NH USA
- Department of Epidemiology, Dartmouth College, Hanover, NH USA
| | - A. James O’Malley
- Department of Biomedical Data Science, Dartmouth College, Hanover, NH USA
- The Dartmouth Institute for Health Policy and Clinical Practice, Dartmouth College, Hanover, NH USA
| |
Collapse
|
24
|
Schaub MT, Li J, Peel L. Hierarchical community structure in networks. Phys Rev E 2023; 107:054305. [PMID: 37329032 DOI: 10.1103/physreve.107.054305] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/24/2020] [Accepted: 04/24/2023] [Indexed: 06/18/2023]
Abstract
Modular and hierarchical community structures are pervasive in real-world complex systems. A great deal of effort has gone into trying to detect and study these structures. Important theoretical advances in the detection of modular have included identifying fundamental limits of detectability by formally defining community structure using probabilistic generative models. Detecting hierarchical community structure introduces additional challenges alongside those inherited from community detection. Here we present a theoretical study on hierarchical community structure in networks, which has thus far not received the same rigorous attention. We address the following questions. (1) How should we define a hierarchy of communities? (2) How do we determine if there is sufficient evidence of a hierarchical structure in a network? (3) How can we detect hierarchical structure efficiently? We approach these questions by introducing a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the popular stochastic block model. We enumerate the challenges involved in detecting hierarchies and, by studying the spectral properties of hierarchical structure, present an efficient and principled method for detecting them.
Collapse
Affiliation(s)
- Michael T Schaub
- Department of Computer Science, RWTH Aachen University, 52074 Aachen, Germany
| | - Jiaze Li
- Department of Data Analytics and Digitalisation, School of Business and Economics, Maastricht University, 6211 LM Maastricht, The Netherlands
| | - Leto Peel
- Department of Data Analytics and Digitalisation, School of Business and Economics, Maastricht University, 6211 LM Maastricht, The Netherlands
| |
Collapse
|
25
|
Ji P, Wang Y, Peron T, Li C, Nagler J, Du J. Structure and function in artificial, zebrafish and human neural networks. Phys Life Rev 2023; 45:74-111. [PMID: 37182376 DOI: 10.1016/j.plrev.2023.04.004] [Citation(s) in RCA: 9] [Impact Index Per Article: 9.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/13/2023] [Accepted: 04/20/2023] [Indexed: 05/16/2023]
Abstract
Network science provides a set of tools for the characterization of the structure and functional behavior of complex systems. Yet a major problem is to quantify how the structural domain is related to the dynamical one. In other words, how the diversity of dynamical states of a system can be predicted from the static network structure? Or the reverse problem: starting from a set of signals derived from experimental recordings, how can one discover the network connections or the causal relations behind the observed dynamics? Despite the advances achieved over the last two decades, many challenges remain concerning the study of the structure-dynamics interplay of complex systems. In neuroscience, progress is typically constrained by the low spatio-temporal resolution of experiments and by the lack of a universal inferring framework for empirical systems. To address these issues, applications of network science and artificial intelligence to neural data have been rapidly growing. In this article, we review important recent applications of methods from those fields to the study of the interplay between structure and functional dynamics of human and zebrafish brain. We cover the selection of topological features for the characterization of brain networks, inference of functional connections, dynamical modeling, and close with applications to both the human and zebrafish brain. This review is intended to neuroscientists who want to become acquainted with techniques from network science, as well as to researchers from the latter field who are interested in exploring novel application scenarios in neuroscience.
Collapse
Affiliation(s)
- Peng Ji
- Institute of Science and Technology for Brain-Inspired Intelligence, Fudan University, Shanghai 200433, China; Key Laboratory of Computational Neuroscience and Brain-Inspired Intelligence, Ministry of Education, Shanghai 200433, China; MOE Frontiers Center for Brain Science, Fudan University, Shanghai 200433, China
| | - Yufan Wang
- Institute of Neuroscience, State Key Laboratory of Neuroscience, Center for Excellence in Brain Science and Intelligence Technology, Chinese Academy of Sciences, 320 Yue-Yang Road, Shanghai 200031, China
| | - Thomas Peron
- Institute of Mathematics and Computer Science, University of São Paulo, São Carlos 13566-590, São Paulo, Brazil.
| | - Chunhe Li
- Shanghai Center for Mathematical Sciences and School of Mathematical Sciences, Fudan University, Shanghai 200433, China; Institute of Science and Technology for Brain-Inspired Intelligence and MOE Frontiers Center for Brain Science, Fudan University, Shanghai 200433, China.
| | - Jan Nagler
- Deep Dynamics, Frankfurt School of Finance & Management, Frankfurt, Germany; Centre for Human and Machine Intelligence, Frankfurt School of Finance & Management, Frankfurt, Germany
| | - Jiulin Du
- Institute of Neuroscience, State Key Laboratory of Neuroscience, Center for Excellence in Brain Science and Intelligence Technology, Chinese Academy of Sciences, 320 Yue-Yang Road, Shanghai 200031, China.
| |
Collapse
|
26
|
Pedigo BD, Powell M, Bridgeford EW, Winding M, Priebe CE, Vogelstein JT. Generative network modeling reveals quantitative definitions of bilateral symmetry exhibited by a whole insect brain connectome. eLife 2023; 12:e83739. [PMID: 36976249 PMCID: PMC10115445 DOI: 10.7554/elife.83739] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/27/2022] [Accepted: 03/27/2023] [Indexed: 03/29/2023] Open
Abstract
Comparing connectomes can help explain how neural connectivity is related to genetics, disease, development, learning, and behavior. However, making statistical inferences about the significance and nature of differences between two networks is an open problem, and such analysis has not been extensively applied to nanoscale connectomes. Here, we investigate this problem via a case study on the bilateral symmetry of a larval Drosophila brain connectome. We translate notions of 'bilateral symmetry' to generative models of the network structure of the left and right hemispheres, allowing us to test and refine our understanding of symmetry. We find significant differences in connection probabilities both across the entire left and right networks and between specific cell types. By rescaling connection probabilities or removing certain edges based on weight, we also present adjusted definitions of bilateral symmetry exhibited by this connectome. This work shows how statistical inferences from networks can inform the study of connectomes, facilitating future comparisons of neural structures.
Collapse
Affiliation(s)
- Benjamin D Pedigo
- Department of Biomedical Engineering, Johns Hopkins UniversityBaltimoreUnited States
| | - Mike Powell
- Department of Biomedical Engineering, Johns Hopkins UniversityBaltimoreUnited States
| | - Eric W Bridgeford
- Department of Biostatistics, Johns Hopkins UniversityBaltimoreUnited States
| | - Michael Winding
- Department of Zoology, University of CambridgeCambridgeUnited Kingdom
- Neurobiology Division, MRC Laboratory of Molecular BiologyCambridgeUnited Kingdom
- Janelia Research Campus, Howard Hughes Medical InstituteAshburnUnited States
| | - Carey E Priebe
- Department of Applied Mathematics and Statistics, Johns Hopkins UniversityBaltimoreUnited States
| | - Joshua T Vogelstein
- Department of Biomedical Engineering, Johns Hopkins UniversityBaltimoreUnited States
| |
Collapse
|
27
|
Shi F, Evans J. Surprising combinations of research contents and contexts are related to impact and emerge with scientific outsiders from distant disciplines. Nat Commun 2023; 14:1641. [PMID: 36964138 PMCID: PMC10039062 DOI: 10.1038/s41467-023-36741-4] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/15/2021] [Accepted: 02/15/2023] [Indexed: 03/26/2023] Open
Abstract
We investigate the degree to which impact in science and technology is associated with surprising breakthroughs, and how those breakthroughs arise. Identifying breakthroughs across science and technology requires models that distinguish surprising from expected advances at scale. Drawing on tens of millions of research papers and patents across the life sciences, physical sciences and patented inventions, and using a hypergraph model that predicts realized combinations of research contents (article keywords) and contexts (cited journals), here we show that surprise in terms of unexpected combinations of contents and contexts predicts outsized impact (within the top 10% of citations). These surprising advances emerge across, rather than within researchers or teams-most commonly when scientists from one field publish problem-solving results to an audience from a distant field. Our approach characterizes the frontier of science and technology as a complex hypergraph drawn from high-dimensional embeddings of research contents and contexts, and offers a measure of path-breaking surprise in science and technology.
Collapse
Affiliation(s)
- Feng Shi
- TigerGraph, 3 Twin Dolphin Dr, St. 225, Redwood City, CA, 94065, USA
- Knowledge Lab, University of Chicago, 1155 E. 60th Street #211, Chicago, IL, 60637, USA
| | - James Evans
- Knowledge Lab, University of Chicago, 1155 E. 60th Street #211, Chicago, IL, 60637, USA.
- Department of Sociology, University of Chicago, 1126 E. 59th St. #420, Chicago, IL, 60637, USA.
- Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, 87501, USA.
| |
Collapse
|
28
|
Qing H. Estimating the Number of Communities in Weighted Networks. ENTROPY (BASEL, SWITZERLAND) 2023; 25:e25040551. [PMID: 37190339 PMCID: PMC10137563 DOI: 10.3390/e25040551] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/07/2023] [Revised: 03/13/2023] [Accepted: 03/22/2023] [Indexed: 05/17/2023]
Abstract
Community detection in weighted networks has been a popular topic in recent years. However, while there exist several flexible methods for estimating communities in weighted networks, these methods usually assume that the number of communities is known. It is usually unclear how to determine the exact number of communities one should use. Here, to estimate the number of communities for weighted networks generated from arbitrary distribution under the degree-corrected distribution-free model, we propose one approach that combines weighted modularity with spectral clustering. This approach allows a weighted network to have negative edge weights and it also works for signed networks. We compare the proposed method to several existing methods and show that our method is more accurate for estimating the number of communities both numerically and empirically.
Collapse
Affiliation(s)
- Huan Qing
- School of Mathematics, China University of Mining and Technology, Xuzhou 221116, China
| |
Collapse
|
29
|
Qing H. Estimating Mixed Memberships in Directed Networks by Spectral Clustering. ENTROPY (BASEL, SWITZERLAND) 2023; 25:345. [PMID: 36832711 PMCID: PMC9955123 DOI: 10.3390/e25020345] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 12/29/2022] [Revised: 02/04/2023] [Accepted: 02/10/2023] [Indexed: 06/18/2023]
Abstract
Community detection is an important and powerful way to understand the latent structure of complex networks in social network analysis. This paper considers the problem of estimating community memberships of nodes in a directed network, where a node may belong to multiple communities. For such a directed network, existing models either assume that each node belongs solely to one community or ignore variation in node degree. Here, a directed degree corrected mixed membership (DiDCMM) model is proposed by considering degree heterogeneity. An efficient spectral clustering algorithm with a theoretical guarantee of consistent estimation is designed to fit DiDCMM. We apply our algorithm to a small scale of computer-generated directed networks and several real-world directed networks.
Collapse
Affiliation(s)
- Huan Qing
- School of Mathematics, China University of Mining and Technology, Xuzhou 221116, China
| |
Collapse
|
30
|
Newman MEJ. Message passing methods on complex networks. Proc Math Phys Eng Sci 2023. [DOI: 10.1098/rspa.2022.0774] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 02/11/2023] Open
Abstract
Networks and network computations have become a primary mathematical tool for analyzing the structure of many kinds of complex systems, ranging from the Internet and transportation networks to biochemical interactions and social networks. A common task in network analysis is the calculation of quantities that reside on the nodes of a network, such as centrality measures, probabilities or model states. In this perspective article we discuss message passing methods, a family of techniques for performing such calculations, based on the propagation of information between the nodes of a network. We introduce the message passing approach with a series of examples, give some illustrative applications and results and discuss the deep connections between message passing and phase transitions in networks. We also point out some limitations of the message passing approach and describe some recently introduced methods that address these limitations.
Collapse
Affiliation(s)
- M. E. J. Newman
- Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, MI 48109, USA
| |
Collapse
|
31
|
Torrisi GL, Garetto M, Leonardi E. Bootstrap percolation on the stochastic block model. BERNOULLI 2023. [DOI: 10.3150/22-bej1475] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/07/2022]
|
32
|
Maekawa S, Sasaki Y, Fletcher G, Onizuka M. GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. INFORM SYST 2023. [DOI: 10.1016/j.is.2023.102195] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 02/13/2023]
|
33
|
Kaiser D, Patwardhan S, Radicchi F. Multiplex reconstruction with partial information. Phys Rev E 2023; 107:024309. [PMID: 36932554 DOI: 10.1103/physreve.107.024309] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/15/2022] [Accepted: 01/26/2023] [Indexed: 06/18/2023]
Abstract
A multiplex is a collection of network layers, each representing a specific type of edges. This appears to be a genuine representation of many real-world systems. However, due to a variety of potential factors, such as limited budget and equipment, or physical impossibility, multiplex data can be difficult to observe directly. Often, only partial information on the layer structure of the system is available, whereas the remaining information is in the form of a single-layer network. In this work we face the problem of reconstructing the hidden multiplex structure of an aggregated network from partial information. We propose an algorithm that leverages the layerwise community structure that can be learned from partial observations to reconstruct the ground-truth topology of the unobserved part of the multiplex. The algorithm is characterized by a computational time that grows linearly with the network size. We perform a systematic study of reconstruction problems for both synthetic and real-world multiplex networks. We show that the ability of the proposed method to solve the reconstruction problem is affected by the heterogeneity of the individual layers and the similarity among the layers. On real-world networks, we observe that the accuracy of the reconstruction saturates quickly as the amount of available information increases. In genetic interaction and scientific collaboration multiplexes, for example, we find that 10% of ground-truth information yields 70% accuracy, while 30% information allows for more than 90% accuracy.
Collapse
Affiliation(s)
- Daniel Kaiser
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, Indiana 47408, USA
| | - Siddharth Patwardhan
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, Indiana 47408, USA
| | - Filippo Radicchi
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, Indiana 47408, USA
| |
Collapse
|
34
|
Miao R, Li T. Informative core identification in complex networks. J R Stat Soc Series B Stat Methodol 2023. [DOI: 10.1093/jrsssb/qkac009] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/30/2023]
Abstract
Abstract
In a complex network, the core component with interesting structures is usually hidden within noninformative connections. The noises and bias introduced by the noninformative component can obscure the salient structure and limit many network modeling procedures’ effectiveness. This paper introduces a novel core–periphery model for the noninformative periphery structure of networks without imposing a specific form of the core. We propose spectral algorithms for core identification for general downstream network analysis tasks under the model. The algorithms enjoy strong performance guarantees and are scalable for large networks. We evaluate the methods by extensive simulation studies demonstrating advantages over multiple traditional core–periphery methods. The methods are also used to extract the core structure from a citation network, which results in a more interpretable hierarchical community detection.
Collapse
Affiliation(s)
- Ruizhong Miao
- Department of Statistics, University of Virginia , Charlottesville, VA , USA
| | - Tianxi Li
- Department of Statistics, University of Virginia , Charlottesville, VA , USA
| |
Collapse
|
35
|
Yanchenko E, Sengupta S. Core-periphery structure in networks: A statistical exposition. STATISTICS SURVEYS 2023. [DOI: 10.1214/23-ss141] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 03/03/2023]
Affiliation(s)
- Eric Yanchenko
- Department of Statistics, North Carolina State University, SAS Hall, 2311 Stinson Dr, Raleigh, NC 27607
| | - Srijan Sengupta
- Department of Statistics, North Carolina State University, SAS Hall, 2311 Stinson Dr, Raleigh, NC 27607
| |
Collapse
|
36
|
Detecting early-warning signals for social emergencies by temporal network sociomarkers. Inf Sci (N Y) 2023. [DOI: 10.1016/j.ins.2023.01.076] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/18/2023]
|
37
|
Liu M, Chato C, Poon AFY. From components to communities: bringing network science to clustering for molecular epidemiology. Virus Evol 2023; 9:vead026. [PMID: 37187604 PMCID: PMC10175948 DOI: 10.1093/ve/vead026] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/25/2022] [Revised: 01/30/2023] [Accepted: 04/17/2023] [Indexed: 05/17/2023] Open
Abstract
Defining clusters of epidemiologically related infections is a common problem in the surveillance of infectious disease. A popular method for generating clusters is pairwise distance clustering, which assigns pairs of sequences to the same cluster if their genetic distance falls below some threshold. The result is often represented as a network or graph of nodes. A connected component is a set of interconnected nodes in a graph that are not connected to any other node. The prevailing approach to pairwise clustering is to map clusters to the connected components of the graph on a one-to-one basis. We propose that this definition of clusters is unnecessarily rigid. For instance, the connected components can collapse into one cluster by the addition of a single sequence that bridges nodes in the respective components. Moreover, the distance thresholds typically used for viruses like HIV-1 tend to exclude a large proportion of new sequences, making it difficult to train models for predicting cluster growth. These issues may be resolved by revisiting how we define clusters from genetic distances. Community detection is a promising class of clustering methods from the field of network science. A community is a set of nodes that are more densely inter-connected relative to the number of their connections to external nodes. Thus, a connected component may be partitioned into two or more communities. Here we describe community detection methods in the context of genetic clustering for epidemiology, demonstrate how a popular method (Markov clustering) enables us to resolve variation in transmission rates within a giant connected component of HIV-1 sequences, and identify current challenges and directions for further work.
Collapse
Affiliation(s)
- Molly Liu
- Department of Pathology and Laboratory Medicine, Western University, Dental Sciences Building, Rm. 4044, London, ON N6A 5C1, Canada
| | - Connor Chato
- Department of Pathology and Laboratory Medicine, Western University, Dental Sciences Building, Rm. 4044, London, ON N6A 5C1, Canada
| | | |
Collapse
|
38
|
Xue M, Wang Z, Zhong F, Wang Y, Xu M, Deussen O, Wang Y. Taurus: Towards a Unified Force Representation and Universal Solver for Graph Layout. IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2023; 29:886-895. [PMID: 36166546 DOI: 10.1109/tvcg.2022.3209371] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/16/2023]
Abstract
Over the past few decades, a large number of graph layout techniques have been proposed for visualizing graphs from various domains. In this paper, we present a general framework, Taurus, for unifying popular techniques such as the spring-electrical model, stress model, and maxent-stress model. It is based on a unified force representation, which formulates most existing techniques as a combination of quotient-based forces that combine power functions of graph-theoretical and Euclidean distances. This representation enables us to compare the strengths and weaknesses of existing techniques, while facilitating the development of new methods. Based on this, we propose a new balanced stress model (BSM) that is able to layout graphs in superior quality. In addition, we introduce a universal augmented stochastic gradient descent (SGD) optimizer that efficiently finds proper solutions for all layout techniques. To demonstrate the power of our framework, we conduct a comprehensive evaluation of existing techniques on a large number of synthetic and real graphs. We release an open-source package, which facilitates easy comparison of different graph layout methods for any graph input as well as effectively creating customized graph layout techniques.
Collapse
|
39
|
Shang R, Zhang W, Li Z, Wang C, Jiao L. Attribute community detection based on latent representation learning and graph regularized non-negative matrix factorization. Appl Soft Comput 2023. [DOI: 10.1016/j.asoc.2022.109932] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/23/2022]
|
40
|
Tjøstheim D, Jullum M, Løland A. Statistical Embedding: Beyond Principal Components. Stat Sci 2023. [DOI: 10.1214/22-sts881] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 02/25/2023]
Affiliation(s)
- Dag Tjøstheim
- Dag Tjøstheim is Professor Emeritus at the Department of Mathematics, University of Bergen, Bergen, Norway and Professor II at the Norwegian Computing Center, Oslo, Norway
| | - Martin Jullum
- Martin Jullum is Senior Research Scientist at the Norwegian Computing Center, Oslo, Norway
| | - Anders Løland
- Anders Løland is Research Director at the Norwegian Computing Center, Oslo, Norway
| |
Collapse
|
41
|
Costa AR, Ralha CG. AC2CD: An actor-critic architecture for community detection in dynamic social networks. Knowl Based Syst 2022. [DOI: 10.1016/j.knosys.2022.110202] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/24/2022]
|
42
|
Kuang J, Scoglio C, Michel K. Feature learning and network structure from noisy node activity data. Phys Rev E 2022; 106:064301. [PMID: 36671154 PMCID: PMC9869472 DOI: 10.1103/physreve.106.064301] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/26/2021] [Accepted: 11/17/2022] [Indexed: 06/17/2023]
Abstract
In the studies of network structures, much attention has been devoted to developing approaches to reconstruct networks and predict missing links when edge-related information is given. However, such approaches are not applicable when we are only given noisy node activity data with missing values. This work presents an unsupervised learning framework to learn node vectors and construct networks from such node activity data. First, we design a scheme to generate random node sequences from node context sets, which are generated from node activity data. Then, a three-layer neural network is adopted training the node sequences to obtain node vectors, which allow us to construct networks and capture nodes with synergistic roles. Furthermore, we present an entropy-based approach to select the most meaningful neighbors for each node in the resulting network. Finally, the effectiveness of the method is validated through both synthetic and real data.
Collapse
Affiliation(s)
- Junyao Kuang
- Department of Electrical and Computer Engineering
| | | | | |
Collapse
|
43
|
Legramanti S, Rigon T, Durante D, Dunson DB. Extended stochastic block models with application to criminal networks. Ann Appl Stat 2022; 16:2369-2395. [DOI: 10.1214/21-aoas1595] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/19/2022]
Affiliation(s)
- Sirio Legramanti
- Department Decision Sciences and Institute for Data Science and Analytics, Bocconi University
| | - Tommaso Rigon
- Department of Economics, Management and Statistics, University of Milano-Bicocca
| | - Daniele Durante
- Department Decision Sciences and Institute for Data Science and Analytics, Bocconi University
| | | |
Collapse
|
44
|
"Stealing fire or stacking knowledge" by machine intelligence to model link prediction in complex networks. iScience 2022; 26:105697. [PMID: 36570772 PMCID: PMC9771718 DOI: 10.1016/j.isci.2022.105697] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/15/2022] [Revised: 09/15/2022] [Accepted: 11/22/2022] [Indexed: 12/02/2022] Open
Abstract
Current methodologies to model connectivity in complex networks either rely on network scientists' intelligence to discover reliable physical rules or use artificial intelligence (AI) that stacks hundreds of inaccurate human-made rules to make a new one that optimally summarizes them together. Here, we provide an accurate and reproducible scientific analysis showing that, contrary to the current belief, stacking more good link prediction rules does not necessarily improve the link prediction performance to nearly optimal as suggested by recent studies. Finally, under the light of our novel results, we discuss the pros and cons of each current state-of-the-art link prediction strategy, concluding that none of the current solutions are what the future might hold for us. Future solutions might require the design and development of next generation "creative" AI that are able to generate and understand complex physical rules for us.
Collapse
|
45
|
Marsman M, Huth K. Idiographic Ising and Divide and Color Models: Encompassing Networks for Heterogeneous Binary Data. MULTIVARIATE BEHAVIORAL RESEARCH 2022:1-28. [PMID: 36434773 DOI: 10.1080/00273171.2022.2135089] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/16/2023]
Abstract
The Ising model is a graphical model that has played an essential role in network psychometrics. It has been used as a theoretical model to conceptualize psychological concepts and as a statistical model to analyze psychological data. Using graphical models such as the Ising model to analyze psychological data has been heavily critiqued since these data often come from cross-sectional applications. An often voiced concern is the inability of the Ising model to express heterogeneity in the population. The idiographic approach has been posed as an alternative and aims to infer individual network structures. While idiographic networks overcome population heterogeneity, it is unclear how they aggregate into established cross-sectional phenomena. This paper establishes a formal bridge between idiographic and cross-sectional network approaches of the Ising model. We ascertain unique topological structures that characterize individuals and aggregate into an Ising model cross-sectionally. This new formulation supports population heterogeneity while being consistent with cross-sectional phenomena. The proposed theory also establishes a new statistical framework for analyzing populations of idiographic networks for binary variables. The Ising model and the divide and color model are special cases of this new framework. We introduce a Gibbs sampling algorithm to estimate models from this new framework.
Collapse
Affiliation(s)
- M Marsman
- Department of Psychology, University of Amsterdam
| | - K Huth
- Department of Psychology, University of Amsterdam
- Department of Psychiatry, Amsterdam University Medical Center
- Centre for Urban Mental Health, University of Amsterdam
| |
Collapse
|
46
|
Qing H, Wang J. Estimating mixed-memberships using the symmetric laplacian inverse matrix. J Korean Stat Soc 2022. [DOI: 10.1007/s42952-022-00199-9] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/22/2022]
|
47
|
Peel L, Peixoto TP, De Domenico M. Statistical inference links data and theory in network science. Nat Commun 2022; 13:6794. [PMID: 36357376 PMCID: PMC9649740 DOI: 10.1038/s41467-022-34267-9] [Citation(s) in RCA: 11] [Impact Index Per Article: 5.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/01/2021] [Accepted: 10/18/2022] [Indexed: 11/11/2022] Open
Abstract
The number of network science applications across many different fields has been rapidly increasing. Surprisingly, the development of theory and domain-specific applications often occur in isolation, risking an effective disconnect between theoretical and methodological advances and the way network science is employed in practice. Here we address this risk constructively, discussing good practices to guarantee more successful applications and reproducible results. We endorse designing statistically grounded methodologies to address challenges in network science. This approach allows one to explain observational data in terms of generative models, naturally deal with intrinsic uncertainties, and strengthen the link between theory and applications. Theoretical models and structures recovered from measured data serve for analysis of complex networks. The authors discuss here existing gaps between theoretical methods and real-world applied networks, and potential ways to improve the interplay between theory and applications.
Collapse
|
48
|
Probabilistic program inference in network-based epidemiological simulations. PLoS Comput Biol 2022; 18:e1010591. [DOI: 10.1371/journal.pcbi.1010591] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/12/2021] [Revised: 11/17/2022] [Accepted: 09/21/2022] [Indexed: 11/09/2022] Open
Abstract
Accurate epidemiological models require parameter estimates that account for mobility patterns and social network structure. We demonstrate the effectiveness of probabilistic programming for parameter inference in these models. We consider an agent-based simulation that represents mobility networks as degree-corrected stochastic block models, whose parameters we estimate from cell phone co-location data. We then use probabilistic program inference methods to approximate the distribution over disease transmission parameters conditioned on reported cases and deaths. Our experiments demonstrate that the resulting models improve the quality of fit in multiple geographies relative to baselines that do not model network topology.
Collapse
|
49
|
Barbarino G, Noferini V, Van Dooren P. Role extraction for digraphs via neighborhood pattern similarity. Phys Rev E 2022; 106:054301. [PMID: 36559511 DOI: 10.1103/physreve.106.054301] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/10/2022] [Accepted: 10/06/2022] [Indexed: 12/24/2022]
Abstract
We analyze the recovery of different roles in a network modeled by a directed graph, based on the so-called Neighborhood Pattern Similarity approach. Our analysis uses results from random matrix theory to show that, when assuming that the graph is generated as a particular stochastic block model with Bernoulli probability distributions for the different blocks, then the recovery is asymptotically correct when the graph has a sufficiently large dimension. Under these assumptions there is a sufficient gap between the dominant and dominated eigenvalues of the similarity matrix, which guarantees the asymptotic correct identification of the number of different roles. We also comment on the connections with the literature on stochastic block models, including the case of probabilities of order log(n)/n where n is the graph size. We provide numerical experiments to assess the effectiveness of the method when applied to practical networks of finite size.
Collapse
Affiliation(s)
- Giovanni Barbarino
- Aalto University, Department of Mathematics and Systems Analysis, P.O. Box 11100, FI-00076 Aalto, Finland
| | - Vanni Noferini
- Aalto University, Department of Mathematics and Systems Analysis, P.O. Box 11100, FI-00076 Aalto, Finland
| | - Paul Van Dooren
- Université catholique de Louvain, Department of Mathematical Engineering, Av. Lemaitre 4, B-1348 Louvain-la-Neuve, Belgium
| |
Collapse
|
50
|
Li HJ, Song S, Tan W, Huang Z, Li X, Xu W, Cao J. Characterizing the fuzzy community structure in link graph via the likelihood optimization. Neurocomputing 2022. [DOI: 10.1016/j.neucom.2022.09.013] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/31/2022]
|