Improved brain community structure detection by two-step weighted modularity maximization

The human brain can be regarded as a complex network with interacting connections between brain regions. Complex brain network analyses have been widely applied to functional magnetic resonance imaging (fMRI) data and have revealed the existence of community structures in brain networks. The identification of communities may provide insight into understanding the topological functions of brain networks. Among various community detection methods, the modularity maximization (MM) method has the advantages of model conciseness, fast convergence and strong adaptability to large-scale networks and has been extended from single-layer networks to multilayer networks to investigate the community structure changes of brain networks. However, the problems of MM, suffering from instability and failing to detect hierarchical community structure in networks, largely limit the application of MM in the community detection of brain networks. In this study, we proposed the weighted modularity maximization (WMM) method by using the weight matrix to weight the adjacency matrix and improve the performance of MM. Moreover, we further proposed the two-step WMM method to detect the hierarchical community structures of networks by utilizing node attributes. The results of the synthetic networks without node attributes demonstrated that WMM showed better partition accuracy than both MM and robust MM and better stability than MM. The two-step WMM method showed better accuracy of community partitioning than WMM for synthetic networks with node attributes. Moreover, the results of resting state fMRI (rs-fMRI) data showed that two-step WMM had the advantage of detecting the hierarchical communities over WMM and was more insensitive to the density of the rs-fMRI networks than WMM.

The Bayesian Cut

An important task in the analysis of graphs is separating nodes into densely connected groups with little interaction between each other. Prominent methods here include flow based graph cutting procedures as well as statistical network modeling approaches. However, adequately accounting for this, the so-called community structure, in complex networks remains a major challenge. We present a novel generic Bayesian probabilistic model for graph cutting in which we derive an analytical solution to the marginalization of nuisance parameters under constraints enforcing community structure. As a part of the solution a large scale approximation for integrals involving multiple incomplete gamma functions is derived. Our multiple cluster solution presents a generic tool for Bayesian inference on Poisson weighted graphs across different domains. Applied on three real world social networks as well as three image segmentation problems our approach shows on par or better performance to existing spectral graph cutting and community detection methods, while learning the underlying parameter space. The developed procedure provides a principled statistical framework for graph cutting and the Bayesian Cut source code provided enables easy adoption of the procedure as an alternative to existing graph cutting methods.

Multi-subject Stochastic Blockmodels for adaptive analysis of individual differences in human brain network cluster structure

There is considerable interest in elucidating the cluster structure of brain networks in terms of modules, blocks or clusters of similar nodes. However, it is currently challenging to handle data on multiple subjects since most of the existing methods are applicable only on a subject-by-subject basis or for analysis of an average group network. The main limitation of per-subject models is that there is no obvious way to combine the results for group comparisons, and of group-averaged models that they do not reflect the variability between subjects. Here, we propose two new extensions of the classical Stochastic Blockmodel (SBM) that use a mixture model to estimate blocks or clusters of connected nodes, combined with a regression model to capture the effects of subject-level covariates on individual differences in cluster structure. The proposed Multi-Subject Stochastic Blockmodels (MS-SBMs) can flexibly account for between-subject variability in terms of homogeneous or heterogeneous covariate effects on connectivity using subject demographics such as age or diagnostic status. Using synthetic data, representing a range of block sizes and cluster structures, we investigate the accuracy of the estimated MS-SBM parameters as well as the validity of inference procedures based on the Wald, likelihood ratio and permutation tests. We show that the proposed multi-subject SBMs recover the true cluster structure of synthetic networks more accurately and adaptively than standard methods for modular decomposition (i.e. the Fast Louvain and Newman Spectral algorithms). Permutation tests of MS-SBM parameters were more robustly valid for statistical inference and Type I error control than tests based on standard asymptotic assumptions. Applied to analysis of multi-subject resting-state fMRI networks (13 healthy volunteers; 12 people with schizophrenia; n=268 brain regions), we show that Heterogeneous Stochastic Blockmodel (Het-SBM) identifies a range of network topologies simultaneously, including modular and core structures.

Finding Communities by Their Centers

Detecting communities or clusters in a real-world, networked system is of considerable interest in various fields such as sociology, biology, physics, engineering science, and interdisciplinary subjects, with significant efforts devoted in recent years. Many existing algorithms are only designed to identify the composition of communities, but not the structures. Whereas we believe that the local structures of communities can also shed important light on their detection. In this work, we develop a simple yet effective approach that simultaneously uncovers communities and their centers. The idea is based on the premise that organization of a community generally can be viewed as a high-density node surrounded by neighbors with lower densities, and community centers reside far apart from each other. We propose so-called “community centrality” to quantify likelihood of a node being the community centers in such a landscape, and then propagate multiple, significant center likelihood throughout the network via a diffusion process. Our approach is an efficient linear algorithm, and has demonstrated superior performance on a wide spectrum of synthetic and real world networks especially those with sparse connections amongst the community centers.

Non-parametric Bayesian graph models reveal community structure in resting state fMRI

Modeling of resting state functional magnetic resonance imaging (rs-fMRI) data using network models is of increasing interest. It is often desirable to group nodes into clusters to interpret the communication patterns between nodes. In this study we consider three different nonparametric Bayesian models for node clustering in complex networks. In particular, we test their ability to predict unseen data and their ability to reproduce clustering across datasets. The three generative models considered are the Infinite Relational Model (IRM), Bayesian Community Detection (BCD), and the Infinite Diagonal Model (IDM). The models define probabilities of generating links within and between clusters and the difference between the models lies in the restrictions they impose upon the between-cluster link probabilities. IRM is the most flexible model with no restrictions on the probabilities of links between clusters. BCD restricts the between-cluster link probabilities to be strictly lower than within-cluster link probabilities to conform to the community structure typically seen in social networks. IDM only models a single between-cluster link probability, which can be interpreted as a background noise probability. These probabilistic models are compared against three other approaches for node clustering, namely Infomap, Louvain modularity, and hierarchical clustering. Using 3 different datasets comprising healthy volunteers' rs-fMRI we found that the BCD model was in general the most predictive and reproducible model. This suggests that rs-fMRI data exhibits community structure and furthermore points to the significance of modeling heterogeneous between-cluster link probabilities.