A weighted prior tensor train decomposition method for community detection in multi-layer networks.

Community detection in multi-layer networks stands as a prominent subject within network analysis research. However, the majority of existing techniques for identifying communities encounter two primary constraints: they lack suitability for high-dimensional data within multi-layer networks and fail to fully leverage additional auxiliary information among communities to enhance detection accuracy. To address these limitations, a novel approach named weighted prior tensor training decomposition (WPTTD) is proposed for multi-layer network community detection. Specifically, the WPTTD method harnesses the tensor feature optimization techniques to effectively manage high-dimensional data in multi-layer networks. Additionally, it employs a weighted flattened network to construct prior information for each dimension of the multi-layer network, thereby continuously exploring inter-community connections. To preserve the cohesive structure of communities and to harness comprehensive information within the multi-layer network for more effective community detection, the common community manifold learning (CCML) is integrated into the WPTTD framework for enhancing the performance. Experimental evaluations conducted on both artificial and real-world networks have verified that this algorithm outperforms several mainstream multi-layer network community detection algorithms.

Densely sampled stimulus-response map of human cortex with single pulse TMS-EEG and its relation to whole brain neuroimaging measures.

Large-scale networks underpin brain functions. How such networks respond to focal stimulation can help decipher complex brain processes and optimize brain stimulation treatments. To map such stimulation-response patterns across the brain non-invasively, we recorded concurrent EEG responses from single-pulse transcranial magnetic stimulation (i.e., TMS-EEG) from over 100 cortical regions with two orthogonal coil orientations from one densely-sampled individual. We also acquired Human Connectome Project (HCP)-styled diffusion imaging scans (six), resting-state functional Magnetic Resonance Imaging (fMRI) scans (120 mins), resting-state EEG scans (108 mins), and structural MR scans (T1- and T2-weighted). Using the TMS-EEG data, we applied network science-based community detection to reveal insights about the brain's causal-functional organization from both a stimulation and recording perspective. We also computed structural and functional maps and the electric field of each TMS stimulation condition. Altogether, we hope the release of this densely sampled (n=1) dataset will be a uniquely valuable resource for both basic and clinical neuroscience research.

Distinct Network Patterns Emerge from Cartesian and XOR Epistasis Models: A Comparative Network Science Analysis.

Background: Epistasis, the phenomenon where the effect of one gene (or variant) is masked or modified by one or more other genes, can significantly contribute to the observed phenotypic variance of complex traits. To date, it has been generally assumed that genetic interactions can be detected using a Cartesian, or multiplicative, interaction model commonly utilized in standard regression approaches. However, a recent study investigating epistasis in obesity-related traits in rats and mice has identified potential limitations of the Cartesian model, revealing that it only detects some of the genetic interactions occurring in these systems. By applying an alternative approach, the exclusive-or (XOR) model, the researchers detected a greater number of epistatic interactions and identified more biologically relevant ontological terms associated with the interacting loci. This suggests that the XOR model may provide a more comprehensive understanding of epistasis in these species and phenotypes. To further explore these findings and determine if different interaction models also make up distinct epistatic networks, we leverage network science to provide a more comprehensive view into the genetic interactions underlying BMI in this system. Results: Our comparative analysis of networks derived from Cartesian and XOR interaction models in rats (Rattus norvegicus) uncovers distinct topological characteristics for each model-derived network. Notably, we discover that networks based on the XOR model exhibit an enhanced sensitivity to epistatic interactions. This sensitivity enables the identification of network communities, revealing novel trait-related biological functions through enrichment analysis. Furthermore, we identify triangle network motifs in the XOR epistatic network, suggestive of higher-order epistasis, based on the topology of lower-order epistasis. Conclusions: These findings highlight the XOR model's ability to uncover meaningful biological associations as well as higher-order epistasis from lower-order epistatic networks. Additionally, our results demonstrate that network approaches not only enhance epistasis detection capabilities but also provide more nuanced understandings of genetic architectures underlying complex traits. The identification of community structures and motifs within these distinct networks, especially in XOR, points to the potential for network science to aid in the discovery of novel genetic pathways and regulatory networks. Such insights are important for advancing our understanding of phenotype-genotype relationships.

The multiscale topological organization of the functional brain network in adolescent PTSD.

The experience of an extremely aversive event can produce enduring deleterious behavioral, and neural consequences, among which posttraumatic stress disorder (PTSD) is a representative example. Although adolescence is a period of great exposure to potentially traumatic events, the effects of trauma during adolescence remain understudied in clinical neuroscience. In this exploratory work, we aim to study the whole-cortex functional organization of 14 adolescents with PTSD using a data-driven method tailored to our population of interest. To do so, we built on the network neuroscience framework and specifically on multilayer (multisubject) community analysis to study the functional connectivity of the brain. We show, across different topological scales (the number of communities composing the cortex), a hyper-colocalization between regions belonging to occipital and pericentral regions and hypo-colocalization in middle temporal, posterior-anterior medial, and frontal cortices in the adolescent PTSD group compared to a nontrauma exposed group of adolescents. These preliminary results raise the question of an altered large-scale cortical organization in adolescent PTSD, opening an interesting line of research for future investigations.

Dual-learning Multi-hop Nonnegative Matrix Factorization for community detection.

As an important branch of network science, community detection has garnered significant attention. Among various community detection methods, nonnegative matrix factorization (NMF)-based community detection approaches have become a popular research topic. However, most NMF-based methods overlook the network's multi-hop information, let alone the community detection results specific to each hop of the network. In this paper, we propose Dual-learning Multi-hop NMF (DL-MHNMF), a method that considers not only the multi-hop connectivity between two nodes but also factors in the shared results across multiple hops and the impact of differences in the specific results at each hop on the shared outcomes. An efficient iterative optimization algorithm with guaranteed theoretical convergence is proposed for solving DL-MHNMF. Methodologically, by iteratively removing the specific results during the optimization process of DL-MHNMF, we achieve enhanced detection accuracy, which is also verified by subsequent experiments. Specifically, we compare fourteen algorithms on eleven publicly available datasets, and experimental results show that our algorithm outperforms most state-of-the-art methods. The source code is availiable at https://github.com/bx20000827/DL-MHNMF.git.

Comparing the Clique Percolation algorithm to other overlapping community detection algorithms in psychological networks: A Monte Carlo simulation study.

In psychological networks, one limitation of the most used community detection algorithms is that they can only assign each node (symptom) to a unique community, without being able to identify overlapping symptoms. The clique percolation (CP) is an algorithm that identifies overlapping symptoms but its performance has not been evaluated in psychological networks. In this study, we compare the CP with model parameters chosen based on fuzzy modularity (CPMod) with two other alternatives, the ratio of the two largest communities (CPRat), and entropy (CPEnt). We evaluate their performance to: (1) identify the correct number of latent factors (i.e., communities); and (2) identify the observed variables with substantive (and equally sized) cross-loadings (i.e., overlapping symptoms). We carried out simulations under 972 conditions (3x2x2x3x3x3x3): (1) data categories (continuous, polytomous and dichotomous); (2) number of factors (two and four); (3) number of observed variables per factor (four and eight); (4) factor correlations (0.0, 0.5, and 0.7); (5) size of primary factor loadings (0.40, 0.55, and 0.70); (6) proportion of observed variables with substantive cross-loadings (0.0%, 12.5%, and 25.0%); and (7) sample size (300, 500, and 1000). Performance was evaluated through the Omega index, Mean Bias Error (MBE), Mean Absolute Error (MAE), sensitivity, specificity, and mean number of isolated nodes. We also evaluated two other methods, Exploratory Factor Analysis and the Walktrap algorithm modified to consider overlap (EFA-Ov and Walk-Ov, respectively). The Walk-Ov displayed the best performance across most conditions and is the recommended option to identify communities with overlapping symptoms in psychological networks.

Simple-based Dynamic Decentralized Community Detection Algorithm in socially aware networks.

This paper introduces a novel, Simple-based Dynamic Decentralized Community Detection Algorithm (S-DCDA) for Socially Aware Networks. This algorithm aims to address the resource-intensive nature, instabilities and inaccuracies of traditional distributed community detection algorithms. The dynamics of decentralization is evident in the threefold nature of the algorithm: (i) each node of the community is the core of the entire network or community for a certain period of time dependent on their need, (ii) nodes are not centralized around themselves, requiring the consent of the other node to join a community, and (iii) Communities start from a single node to form an initial scale community, the number of nodes and the relationship among them are constantly changing. The algorithm requires low processor performance and memory capacity size of each node, to a certain extent, effectively improve the accuracy and stability of community detection and maintenance. Experimental results demonstrate that in comparison to classical and classical-based improved community detection algorithms, S-DCDA yields superior detection results.

scMLC: an accurate and robust multiplex community detection method for single-cell multi-omics data.

Clustering cells based on single-cell multi-modal sequencing technologies provides an unprecedented opportunity to create high-resolution cell atlas, reveal cellular critical states and study health and diseases. However, effectively integrating different sequencing data for cell clustering remains a challenging task. Motivated by the successful application of Louvain in scRNA-seq data, we propose a single-cell multi-modal Louvain clustering framework, called scMLC, to tackle this problem. scMLC builds multiplex single- and cross-modal cell-to-cell networks to capture modal-specific and consistent information between modalities and then adopts a robust multiplex community detection method to obtain the reliable cell clusters. In comparison with 15 state-of-the-art clustering methods on seven real datasets simultaneously measuring gene expression and chromatin accessibility, scMLC achieves better accuracy and stability in most datasets. Synthetic results also indicate that the cell-network-based integration strategy of multi-omics data is superior to other strategies in terms of generalization. Moreover, scMLC is flexible and can be extended to single-cell sequencing data with more than two modalities.

Community detection in the human connectome: Method types, differences and their impact on inference.

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 from n $$ n $$ = 5251 pre/early adolescents in the adolescent brain cognitive development [ABCD] study), and n $$ 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.

Game Theoretic Clustering for Finding Strong Communities.

We address the challenge of identifying meaningful communities by proposing a model based on convex game theory and a measure of community strength. Many existing community detection methods fail to provide unique solutions, and it remains unclear how the solutions depend on initial conditions. Our approach identifies strong communities with a hierarchical structure, visualizable as a dendrogram, and computable in polynomial time using submodular function minimization. This framework extends beyond graphs to hypergraphs or even polymatroids. In the case when the model is graphical, a more efficient algorithm based on the max-flow min-cut algorithm can be devised. Though not achieving near-linear time complexity, the pursuit of practical algorithms is an intriguing avenue for future research. Our work serves as the foundation, offering an analytical framework that yields unique solutions with clear operational meaning for the communities identified.

Multi-grained alignment method based on stable topics in cross-social networks.

The user alignment of cross-social networks is divided into user and group alignments, respectively. Obtaining users' full features is difficult due to social network privacy protection policies in user alignment mode. In contrast, the alignment accuracy is low due to the large number of edge users in the group alignment mode. To resolve this issue, First, stable topics are obtained from user-generated content (UGC) based on embedded topic jitter time, and the weight of user edges is updated by using vector distances. An improved Louvain algorithm, called Stable Topic-Louvain (ST-L), is designed to accomplish multi-level community detection without predetermined tags. It aims to obtain fuzzy topic features of the community and finalize the community alignment across social networks. Furthermore, iterative alignment is executed from coarse-grained communities to fine-grained sub-communities until user-level alignment occurs. The process can be terminated at any layer to achieve multi-granularity alignment, which resolves the low accuracy issue of edge user alignment at a single granularity and improves the accuracy of user alignment. The effectiveness of the proposed method is shown by implementing real datasets.

Multi-omics analysis reveals epigenetically regulated processes and patient classification in lung adenocarcinoma.

Aberrant DNA methylation is a hallmark of many cancer types. Despite our knowledge of epigenetic and transcriptomic alterations in lung adenocarcinoma (LUAD), we lack robust multi-modal molecular classifications for patient stratification. This is partly because the impact of epigenetic alterations on lung cancer development and progression is still not fully understood. To that end, we identified disease-associated processes under epigenetic regulation in LUAD. We performed a genome-wide expression-methylation Quantitative Trait Loci (emQTL) analysis by integrating DNA methylation and gene expression data from 453 patients in the TCGA cohort. Using a community detection algorithm, we identified distinct communities of CpG-gene associations with diverse biological processes. Interestingly, we identified a community linked to hormone response and lipid metabolism; the identified CpGs in this community were enriched in enhancer regions and binding regions of transcription factors such as FOXA1/2, GRHL2, HNF1B, AR, and ESR1. Furthermore, the CpGs were connected to their associated genes through chromatin interaction loops. These findings suggest that the expression of genes involved in hormone response and lipid metabolism in LUAD is epigenetically regulated through DNA methylation and enhancer-promoter interactions. By applying consensus clustering on the integrated expression-methylation pattern of the emQTL-genes and CpGs linked to hormone response and lipid metabolism, we further identified subclasses of patients with distinct prognoses. This novel patient stratification was validated in an independent patient cohort of 135 patients and showed increased prognostic significance compared to previously defined molecular subtypes.

Subgrouping with Chain Graphical VAR Models.

Recent years have seen the emergence of an "idio-thetic" class of methods to bridge the gap between nomothetic and idiographic inference. These methods describe nomothetic trends in idiographic processes by pooling intraindividual information across individuals to inform group-level inference or vice versa. The current work introduces a novel "idio-thetic" model: the subgrouped chain graphical vector autoregression (scGVAR). The scGVAR is unique in its ability to identify subgroups of individuals who share common dynamic network structures in both lag(1) and contemporaneous effects. Results from Monte Carlo simulations indicate that the scGVAR shows promise over similar approaches when clusters of individuals differ in their contemporaneous dynamics and in showing increased sensitivity in detecting nuanced group differences while keeping Type-I error rates low. In contrast, a competing approach-the Alternating Least Squares VAR (ALS VAR) performs well when groups were separated by larger distances. Further considerations are provided regarding applications of the ALS VAR and scGVAR on real data and the strengths and limitations of both methods.

Community detection with Greedy Modularity disassembly strategy.

Community detection recognizes groups of densely connected nodes across networks, one of the fundamental procedures in network analysis. This research boosts the standard but locally optimized Greedy Modularity algorithm for community detection. We introduce innovative exploration techniques that include a variety of node and community disassembly strategies. These strategies include methods like non-triad creating, feeble, random as well as inadequate embeddedness for nodes, as well as low internal edge density, low triad participation ratio, weak, low conductance as well as random tactics for communities. We present a methodology that showcases the improvement in modularity across the wide variety of real-world and synthetic networks over the standard approaches. A detailed comparison against other well-known community detection algorithms further illustrates the better performance of our improved method. This study not only optimizes the process of community detection but also broadens the scope for a more nuanced and effective network analysis that may pave the way for more insights as to the dynamism and structures of its functioning by effectively addressing and overcoming the limitations that are inherently attached with the existing community detection algorithms.

Improving the Walktrap Algorithm Using K-Means Clustering.

The walktrap algorithm is one of the most popular community-detection methods in psychological research. Several simulation studies have shown that it is often effective at determining the correct number of communities and assigning items to their proper community. Nevertheless, it is important to recognize that the walktrap algorithm relies on hierarchical clustering because it was originally developed for networks much larger than those encountered in psychological research. In this paper, we present and demonstrate a computational alternative to the hierarchical algorithm that is conceptually easier to understand. More importantly, we show that better solutions to the sum-of-squares optimization problem that is heuristically tackled by hierarchical clustering in the walktrap algorithm can often be obtained using exact or approximate methods for K-means clustering. Three simulation studies and analyses of empirical networks were completed to assess the impact of better sum-of-squares solutions.

GSLAlign: community detection and local PPI network alignment.

High throughput protein-protein interaction (PPI) profiling and computational techniques have resulted in generating a large amount of PPI network data. The study of PPI networks helps in understanding the biological processes of the proteins. The comparative study of the PPI networks helps in identifying the conserved interactions across the species. This article presents a novel local PPI network aligner 'GSLAlign' that consists of two stages. It first detects the communities from the PPI networks by applying the GraphSAGE algorithm using gene expression data. In the second stage, the detected communities are aligned using a community aligner that is based on protein sequence similarity. The community detection algorithm produces more separable and biologically accurate communities as compared to previous community detection algorithms. Moreover, the proposed community alignment algorithm achieves 3-8% better results in terms of semantic similarity as compared to previous local aligners. The average connectivity and coverage of the proposed algorithm are also better than the existing aligners.Communicated by Ramaswamy H. Sarma.

Uncertainty in GNN Learning Evaluations: A Comparison between Measures for Quantifying Randomness in GNN Community Detection.

(1) The enhanced capability of graph neural networks (GNNs) in unsupervised community detection of clustered nodes is attributed to their capacity to encode both the connectivity and feature information spaces of graphs. The identification of latent communities holds practical significance in various domains, from social networks to genomics. Current real-world performance benchmarks are perplexing due to the multitude of decisions influencing GNN evaluations for this task. (2) Three metrics are compared to assess the consistency of algorithm rankings in the presence of randomness. The consistency and quality of performance between the results under a hyperparameter optimisation with the default hyperparameters is evaluated. (3) The results compare hyperparameter optimisation with default hyperparameters, revealing a significant performance loss when neglecting hyperparameter investigation. A comparison of metrics indicates that ties in ranks can substantially alter the quantification of randomness. (4) Ensuring adherence to the same evaluation criteria may result in notable differences in the reported performance of methods for this task. The W randomness coefficient, based on the Wasserstein distance, is identified as providing the most robust assessment of randomness.

Increased Segregation in Functional Connectivity Networks When Watching Unpleasant Arousing Videos: A Generalized Psychophysiological Interaction Analysis.

Background: Properties of functional connectivity (FC), such as network integration and segregation, are shown to be associated with various human behaviors. For example, Godwin et al. and Sun et al. found increased integration with attention allocation, whereas Cohen and D'Esposito and Shine et al. observed increased segregation with simple motor tasks. The current study investigated how viewing video clips with different valence and arousal influenced integration-segregation properties in task-based FC networks. Methods: We analyzed an open dataset collected by Kim et al. We performed a generalized psychophysiological interaction (gPPI) analysis paired with network analysis and community detection to investigate changes in brain network dynamics when people watched four types of videos that differed by affective valence (unpleasant or pleasant) and arousal (arousing or calm). Results: Results showed that unpleasant arousing videos produced greater FC deviation from the baseline (task-induced FC deviation [tiFCd]) and perturbed the brain into a more segregated state than other kinds of video. Increased segregation was only observed in association systems, not sensorimotor systems. Discussion: Unpleasant arousing content perturbed the brain to a functionally distinct state from the other three types of affective videos. We suggest that the change in brain state was related to people disengaging from the unpleasant arousing content or, alternatively, staying alert while exposed to unpleasant arousing stimuli. The study also added to our understanding of how combining task-based gPPI analysis with community detection methods and network segregation measures can advance our knowledge of the links between behavior and brain state changes. Impact statement Network integration and segregation is an important property of the human brain. We address the question of how affective stimuli influence brain dynamics from a functional connectivity (FC) network integration-segregation perspective. By conducting a whole-brain generalized psychophysiological interaction (gPPI) analysis paired with community detection methods, we found that highly aversive video content induced significant FC changes and perturbed the brain to a more segregated state.

Comparing community detection algorithms in psychometric networks: A Monte Carlo simulation.

Identifying the correct number of factors in multivariate data is fundamental to psychological measurement. Factor analysis has a long tradition in the field, but it has been challenged recently by exploratory graph analysis (EGA), an approach based on network psychometrics. EGA first estimates a network and then applies the Walktrap community detection algorithm. Simulation studies have demonstrated that EGA has comparable or better accuracy for recovering the same number of communities as there are factors in the simulated data than factor analytic methods. Despite EGA's effectiveness, there has yet to be an investigation into whether other sparsity induction methods or community detection algorithms could achieve equivalent or better performance. Furthermore, unidimensional structures are fundamental to psychological measurement yet they have been sparsely studied in simulations using community detection algorithms. In the present study, we performed a Monte Carlo simulation using the zero-order correlation matrix, GLASSO, and two variants of a non-regularized partial correlation sparsity induction methods with several community detection algorithms. We examined the performance of these method-algorithm combinations in both continuous and polytomous data across a variety of conditions. The results indicate that the Fast-greedy, Louvain, and Walktrap algorithms paired with the GLASSO method were consistently among the most accurate and least-biased overall.

Aberrant Functional Connectivity in Core-Periphery Structure Based on WSBM in ADHD.

OBJECTIVE: Brain network studies have revealed that the community structure of ADHD is altered. However, these studies have only focused on modular community structure, ignoring the core-periphery community structure. METHOD: This paper employed the weighted stochastic block model to divide the functional connectivity (FC) into 10 communities. And we adopted core score to define the core-periphery structure of FC. Finally, connectivity strength (CS) and disruption index (DI) were used to evaluate the changes of core-periphery structure in ADHD. RESULTS: The core community of visual network showed reduced CS and a positive value of DI, while the CS of periphery community was enhanced. In addition, the interaction between core communities (involving the sensorimotor and visual network) and periphery community of attention network showed increased CS and a negative valve of DI. CONCLUSION: Anomalies in core-periphery community structure provide a new perspective for understanding the community structure of ADHD.