Community detection algorithms: a comparative analysis

Fragmenting networks by targeting collective influencers at a mesoscopic level

A practical approach to protecting networks against epidemic processes such as spreading of infectious diseases, malware, and harmful viral information is to remove some influential nodes beforehand to fragment the network into small components. Because determining the optimal order to remove nodes is a computationally hard problem, various approximate algorithms have been proposed to efficiently fragment networks by sequential node removal. Morone and Makse proposed an algorithm employing the non-backtracking matrix of given networks, which outperforms various existing algorithms. In fact, many empirical networks have community structure, compromising the assumption of local tree-like structure on which the original algorithm is based. We develop an immunization algorithm by synergistically combining the Morone-Makse algorithm and coarse graining of the network in which we regard a community as a supernode. In this way, we aim to identify nodes that connect different communities at a reasonable computational cost. The proposed algorithm works more efficiently than the Morone-Makse and other algorithms on networks with community structure.

Community detection in weighted brain connectivity networks beyond the resolution limit

Graph theory provides a powerful framework to investigate brain functional connectivity networks and their modular organization. However, most graph-based methods suffer from a fundamental resolution limit that may have affected previous studies and prevented detection of modules, or "communities", that are smaller than a specific scale. Surprise, a resolution-limit-free function rooted in discrete probability theory, has been recently introduced and applied to brain networks, revealing a wide size-distribution of functional modules (Nicolini and Bifone, 2016), in contrast with many previous reports. However, the use of Surprise is limited to binary networks, while brain networks are intrinsically weighted, reflecting a continuous distribution of connectivity strengths between different brain regions. Here, we propose Asymptotical Surprise, a continuous version of Surprise, for the study of weighted brain connectivity networks, and validate this approach in synthetic networks endowed with a ground-truth modular structure. We compare Asymptotical Surprise with leading community detection methods currently in use and show its superior sensitivity in the detection of small modules even in the presence of noise and intersubject variability such as those observed in fMRI data. We apply our novel approach to functional connectivity networks from resting state fMRI experiments, and demonstrate a heterogeneous modular organization, with a wide distribution of clusters spanning multiple scales. Finally, we discuss the implications of these findings for the identification of connector hubs, the brain regions responsible for the integration of the different network elements, showing that the improved resolution afforded by Asymptotical Surprise leads to a different classification compared to current methods.

•

Methods to study modularity of brain connectivity networks have a resolution limit.

•

Asymptotical Surprise, a nearly resolution-limit-free method for weighted graphs, is proposed.

•

Improved sensitivity and specificity are demonstrated in model networks.

•

Resting state functional connectivity networks consist of heterogeneous modules.

•

Classification of hubs in function connectivity networks should be revised.

Inferring propagation paths for sparsely observed perturbations on complex networks

In a complex system, perturbations propagate by following paths on the network of interactions among the system's units. In contrast to what happens with the spreading of epidemics, observations of general perturbations are often very sparse in time (there is a single observation of the perturbed system) and in "space" (only a few perturbed and unperturbed units are observed). A major challenge in many areas, from biology to the social sciences, is to infer the propagation paths from observations of the effects of perturbation under these sparsity conditions. We address this problem and show that it is possible to go beyond the usual approach of using the shortest paths connecting the known perturbed nodes. Specifically, we show that a simple and general probabilistic model, which we solved using belief propagation, provides fast and accurate estimates of the probabilities of nodes being perturbed.

Complex Network Clustering by a Multi-objective Evolutionary Algorithm Based on Decomposition and Membrane Structure

The field of complex network clustering is gaining considerable attention in recent years. In this study, a multi-objective evolutionary algorithm based on membranes is proposed to solve the network clustering problem. Population are divided into different membrane structures on average. The evolutionary algorithm is carried out in the membrane structures. The population are eliminated by the vector of membranes. In the proposed method, two evaluation objectives termed as Kernel J-means and Ratio Cut are to be minimized. Extensive experimental studies comparison with state-of-the-art algorithms proves that the proposed algorithm is effective and promising.

Network dynamics: quantitative analysis of complex behavior in metabolism, organelles, and cells, from experiments to models and back

Advancing from two core traits of biological systems: multilevel network organization and nonlinearity, we review a host of novel and readily available techniques to explore and analyze their complex dynamic behavior within the framework of experimental-computational synergy. In the context of concrete biological examples, analytical methods such as wavelet, power spectra, and metabolomics-fluxomics analyses, are presented, discussed, and their strengths and limitations highlighted. Further shown is how time series from stationary and nonstationary biological variables and signals, such as membrane potential, high-throughput metabolomics, O₂ and CO₂ levels, bird locomotion, at the molecular, (sub)cellular, tissue, and whole organ and animal levels, can reveal important information on the properties of the underlying biological networks. Systems biology-inspired computational methods start to pave the way for addressing the integrated functional dynamics of metabolic, organelle and organ networks. As our capacity to unravel the control and regulatory properties of these networks and their dynamics under normal or pathological conditions broadens, so is our ability to address endogenous rhythms and clocks to improve health-span in human aging, and to manage complex metabolic disorders, neurodegeneration, and cancer. WIREs Syst Biol Med 2017, 9:e1352. doi: 10.1002/wsbm.1352 For further resources related to this article, please visit the WIREs website.

Comparison method for community detection on brain networks from neuroimaging data

The brain is a complex system consisting of regions dedicated to different brain functions, and higher cognitive functions are realized via information flow between distant brain areas communicating with each other. As such, it is natural to shift towards brain network analysis from mapping of brain functions, for deeper understanding of the brain system. The graph theoretical network metrics measure global or local properties of network topology, but they do not provide any information about the intermediate scale of the network. Community structure analysis is a useful approach to investigate the mesoscale organization of brain network. However, the community detection schemes are yet to be established. In this paper, we propose a method to compare different community detection schemes for neuroimaging data from multiple subjects. To the best of our knowledge, our method is the first attempt to evaluate community detection from multiple-subject data without "ground truth" community and any assumptions about the original network features. To show its feasibility, three community detection algorithms and three different brain atlases were examined using resting-state fMRI functional networks. As it is crucial to find a single group-based community structure as a representative for a group of subjects to allow discussion about brain areas and connections in different conditions on common ground, a number of community detection schemes based on different approaches have been proposed. A non-parametric permutation test on similarity between group-based community structures and individual community structures was used to determine which algorithm or atlas provided the best representative structure of the group. The Normalized Mutual Information (NMI) was computed to measure the similarity between the community structures. We also discuss further issues on community detection using the proposed method.

Metric projection for dynamic multiplex networks

Evolving multiplex networks are a powerful model for representing the dynamics along time of different phenomena, such as social networks, power grids, biological pathways. However, exploring the structure of the multiplex network time series is still an open problem. Here we propose a two-step strategy to tackle this problem based on the concept of distance (metric) between networks. Given a multiplex graph, first a network of networks is built for each time step, and then a real valued time series is obtained by the sequence of (simple) networks by evaluating the distance from the first element of the series. The effectiveness of this approach in detecting the occurring changes along the original time series is shown on a synthetic example first, and then on the Gulf dataset of political events.

A Comparative Analysis of Community Detection Algorithms on Artificial Networks

Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms' computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm's predicting power and the effective computing time.

Neural Network Models

The Artificial Neural Network (ANN) models gained a wide popularity owing to a number of claimed advantages such as biological plausibility, tolerance with respect to errors or noise in the input data, learning ability allowing an adaptability to environmental constraints. Notwithstanding the fact that most of these advantages are not typical only of ANNs, engineers, psychologists and neuroscientists made an extended use of ANN models in a large number of scientific investigations. In most cases, however, these models have been introduced in order to provide optimization tools more useful than the ones commonly used by traditional Optimization Theory. Unfortunately, just the successful performance of ANN models in optimization tasks produced a widespread neglect of the true – and important – objectives pursued by the first promoters of these models. These objectives can be shortly summarized by the manifesto of connectionist psychology, stating that mental processes are nothing but macroscopic phenomena, emergent from the cooperative interaction of a large number of microscopic knowledge units. This statement – wholly in line with the goal of statistical mechanics – can be readily extended to other processes, beyond the mental ones, including social, economic, and, in general, organizational ones. Therefore this chapter has been designed in order to answer a number of related questions, such as: are the ANN models able to grant for the occurrence of this sort of emergence? How can the occurrence of this emergence be empirically detected? How can the emergence produced by ANN models be controlled? In which sense the ANN emergence could offer a new paradigm for the explanation of macroscopic phenomena? Answering these questions induces to focus the chapter on less popular ANNs, such as the recurrent ones, while neglecting more popular models, such as perceptrons, and on less used units, such as spiking neurons, rather than on McCulloch-Pitts neurons. Moreover, the chapter must mention a number of strategies of emergence detection, useful for researchers performing computer simulations of ANN behaviours. Among these strategies it is possible to quote the reduction of ANN models to continuous models, such as the neural field models or the neural mass models, the recourse to the methods of Network Theory and the employment of techniques borrowed by Statistical Physics, like the one based on the Renormalization Group. Of course, owing to space (and mathematical expertise) requirements, most mathematical details of the proposed arguments are neglected, and, to gain more information, the reader is deferred to the quoted literature.

Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale

Overview

Notions of community quality underlie the clustering of networks. While studies surrounding network clustering are increasingly common, a precise understanding of the realtionship between different cluster quality metrics is unknown. In this paper, we examine the relationship between stand-alone cluster quality metrics and information recovery metrics through a rigorous analysis of four widely-used network clustering algorithms—Louvain, Infomap, label propagation, and smart local moving. We consider the stand-alone quality metrics of modularity, conductance, and coverage, and we consider the information recovery metrics of adjusted Rand score, normalized mutual information, and a variant of normalized mutual information used in previous work. Our study includes both synthetic graphs and empirical data sets of sizes varying from 1,000 to 1,000,000 nodes.

Cluster Quality Metrics

We find significant differences among the results of the different cluster quality metrics. For example, clustering algorithms can return a value of 0.4 out of 1 on modularity but score 0 out of 1 on information recovery. We find conductance, though imperfect, to be the stand-alone quality metric that best indicates performance on the information recovery metrics. Additionally, our study shows that the variant of normalized mutual information used in previous work cannot be assumed to differ only slightly from traditional normalized mutual information.

Network Clustering Algorithms

Smart local moving is the overall best performing algorithm in our study, but discrepancies between cluster evaluation metrics prevent us from declaring it an absolutely superior algorithm. Interestingly, Louvain performed better than Infomap in nearly all the tests in our study, contradicting the results of previous work in which Infomap was superior to Louvain. We find that although label propagation performs poorly when clusters are less clearly defined, it scales efficiently and accurately to large graphs with well-defined clusters.

Power-law relations in random networks with communities

Most random graph models are locally tree-like-do not contain short cycles-rendering them unfit for modeling networks with a community structure. We introduce the hierarchical configuration model (HCM), a generalization of the configuration model that includes community structures, while properties such as the size of the giant component, and the size of the giant percolating cluster under bond percolation can still be derived analytically. Viewing real-world networks as realizations of HCM, we observe two previously undiscovered power-law relations: between the number of edges inside a community and the community sizes, and between the number of edges going out of a community and the community sizes. We also relate the power-law exponent τ of the degree distribution with the power-law exponent of the community-size distribution γ. In the case of extremely dense communities (e.g., complete graphs), this relation takes the simple form τ=γ-1.

Structural architecture supports functional organization in the human aging brain at a regionwise and network level

Functional interactions in the brain are constrained by the underlying anatomical architecture, and structural and functional networks share network features such as modularity. Accordingly, age-related changes of structural connectivity (SC) may be paralleled by changes in functional connectivity (FC). We provide a detailed qualitative and quantitative characterization of the SC-FC coupling in human aging as inferred from resting-state blood oxygen-level dependent functional magnetic resonance imaging and diffusion-weighted imaging in a sample of 47 adults with an age range of 18-82. We revealed that SC and FC decrease with age across most parts of the brain and there is a distinct age-dependency of regionwise SC-FC coupling and network-level SC-FC relations. A specific pattern of SC-FC coupling predicts age more reliably than does regionwise SC or FC alone (r = 0.73, 95% CI = [0.7093, 0.8522]). Hence, our data propose that regionwise SC-FC coupling can be used to characterize brain changes in aging. Hum Brain Mapp 37:2645-2661, 2016. © 2016 Wiley Periodicals, Inc.

NMR Characterization of Information Flow and Allosteric Communities in the MAP Kinase p38γ

The intramolecular network structure of a protein provides valuable insights into allosteric sites and communication pathways. However, a straightforward method to comprehensively map and characterize these pathways is not currently available. Here we present an approach to characterize intramolecular network structure using NMR chemical shift perturbations. We apply the method to the mitogen activated protein kinase (MAPK) p38γ. p38γ contains allosteric sites that are conserved among eukaryotic kinases as well as unique to the MAPK family. How these regulatory sites communicate with catalytic residues is not well understood. Using our method, we observe and characterize for the first time information flux between regulatory sites through a conserved kinase infrastructure. This network is accessed, reinforced, and broken in various states of p38γ, reflecting the functional state of the protein. We demonstrate that the approach detects critical junctions in the network corresponding to biologically significant allosteric sites and pathways.

The Productivity of NHLBI-Funded Obesity Research, 1983-2013

OBJECTIVE

To describe and elucidate the time trends of the academic productivity of NHLBI's obesity-related research funding via bibliometric analysis of 30 years of NHLBI-supported obesity-related publications.

METHODS

In total, 3,545 NHLBI-funded obesity-related publications were identified in the Thomson Reuters InCites™ database. Shared references in a community detection algorithm were used to identify publication topics. Characteristics of publications and topical communities were analyzed based on citation count and percentile rank. A percentile rank >90 was considered "highly cited."

RESULTS

Obesity-related publications increased more than 10-fold over 30 years, whereas NHLBI-funded publications only increased twofold NHLBI-funded obesity publications were cited a median of 23 times (IQR 8-55, range 0-2,047, mean 52). Thirty percent of these publications were highly cited compared to the expected ten percent. Six topical communities were present in 1983 compared to 16 in 2013. The most highly cited topical areas were sleep (n = 199 publications, 38% highly cited), cardiovascular morbidity and mortality (n = 277, 36%), obesity correlates and consequences (n = 588, 35%), and asthma and inflammation (n = 283, 35%).

CONCLUSIONS

NHLBI-funded obesity publications have contributed substantially to the obesity literature, with many highly cited. Publications grew in number and topical diversity over 30 years and grew at a faster rate than total NHLBI publications.

Functional network analysis of genes differentially expressed during xylogenesis in soc1ful woody Arabidopsis plants

Many plant genes are known to be involved in the development of cambium and wood, but how the expression and functional interaction of these genes determine the unique biology of wood remains largely unknown. We used the soc1ful loss of function mutant - the woodiest genotype known in the otherwise herbaceous model plant Arabidopsis - to investigate the expression and interactions of genes involved in secondary growth (wood formation). Detailed anatomical observations of the stem in combination with mRNA sequencing were used to assess transcriptome remodeling during xylogenesis in wild-type and woody soc1ful plants. To interpret the transcriptome changes, we constructed functional gene association networks of differentially expressed genes using the STRING database. This analysis revealed functionally enriched gene association hubs that are differentially expressed in herbaceous and woody tissues. In particular, we observed the differential expression of genes related to mechanical stress and jasmonate biosynthesis/signaling during wood formation in soc1ful plants that may be an effect of greater tension within woody tissues. Our results suggest that habit shifts from herbaceous to woody life forms observed in many angiosperm lineages could have evolved convergently by genetic changes that modulate the gene expression and interaction network, and thereby redeploy the conserved wood developmental program.

Community Structure of a Mental Health Internet Support Group: Modularity in User Thread Participation

BACKGROUND

Little is known about the community structure of mental health Internet support groups, quantitatively. A greater understanding of the factors, which lead to user interaction, is needed to explain the design information of these services and future research concerning their utility.

OBJECTIVE

A study was conducted to determine the characteristics of users associated with the subgroup community structure of an Internet support group for mental health issues.

METHODS

A social network analysis of the Internet support group BlueBoard (blueboard.anu.edu.au) was performed to determine the modularity of the community using the Louvain method. Demographic characteristics age, gender, residential location, type of user (consumer, carer, or other), registration date, and posting frequency in subforums (depression, generalized anxiety, social anxiety, panic disorder, bipolar disorder, obsessive compulsive disorder, borderline personality disorder, eating disorders, carers, general (eg, "chit chat"), and suggestions box) of the BlueBoard users were assessed as potential predictors of the resulting subgroup structure.

RESULTS

The analysis of modularity identified five main subgroups in the BlueBoard community. Registration date was found to be the largest contributor to the modularity outcome as observed by multinomial logistic regression. The addition of this variable to the final model containing all other factors improved its classification accuracy by 46.3%, that is, from 37.9% to 84.2%. Further investigation of this variable revealed that the most active and central users registered significantly earlier than the median registration time in each group.

CONCLUSIONS

The five subgroups resembled five generations of BlueBoard in distinct eras that transcended discussion about different mental health issues. This finding may be due to the activity of highly engaged and central users who communicate with many other users. Future research should seek to determine the generalizability of this finding and investigate the role that highly active and central users may play in the formation of this phenomenon.

Community Structure Reveals Biologically Functional Modules in MEF2C Transcriptional Regulatory Network

Gene regulatory networks are useful to understand the activity behind the complex mechanisms in transcriptional regulation. A main goal in contemporary biology is using such networks to understand the systemic regulation of gene expression. In this work, we carried out a systematic study of a transcriptional regulatory network derived from a comprehensive selection of all potential transcription factor interactions downstream from MEF2C, a human transcription factor master regulator. By analyzing the connectivity structure of such network, we were able to find different biologically functional processes and specific biochemical pathways statistically enriched in communities of genes into the network, such processes are related to cell signaling, cell cycle and metabolism. In this way we further support the hypothesis that structural properties of biological networks encode an important part of their functional behavior in eukaryotic cells.

Link-Prediction Enhanced Consensus Clustering for Complex Networks

Many real networks that are collected or inferred from data are incomplete due to missing edges. Missing edges can be inherent to the dataset (Facebook friend links will never be complete) or the result of sampling (one may only have access to a portion of the data). The consequence is that downstream analyses that "consume" the network will often yield less accurate results than if the edges were complete. Community detection algorithms, in particular, often suffer when critical intra-community edges are missing. We propose a novel consensus clustering algorithm to enhance community detection on incomplete networks. Our framework utilizes existing community detection algorithms that process networks imputed by our link prediction based sampling algorithm and merges their multiple partitions into a final consensus output. On average our method boosts performance of existing algorithms by 7% on artificial data and 17% on ego networks collected from Facebook.

Dynamical detection of network communities

A prominent feature of complex networks is the appearance of communities, also known as modular structures. Specifically, communities are groups of nodes that are densely connected among each other but connect sparsely with others. However, detecting communities in networks is so far a major challenge, in particular, when networks evolve in time. Here, we propose a change in the community detection approach. It underlies in defining an intrinsic dynamic for the nodes of the network as interacting particles (based on diffusive equations of motion and on the topological properties of the network) that results in a fast convergence of the particle system into clustered patterns. The resulting patterns correspond to the communities of the network. Since our detection of communities is constructed from a dynamical process, it is able to analyse time-varying networks straightforwardly. Moreover, for static networks, our numerical experiments show that our approach achieves similar results as the methodologies currently recognized as the most efficient ones. Also, since our approach defines an N-body problem, it allows for efficient numerical implementations using parallel computations that increase its speed performance.

Clustering Scientific Publications Based on Citation Relations: A Systematic Comparison of Different Methods

Clustering methods are applied regularly in the bibliometric literature to identify research areas or scientific fields. These methods are for instance used to group publications into clusters based on their relations in a citation network. In the network science literature, many clustering methods, often referred to as graph partitioning or community detection techniques, have been developed. Focusing on the problem of clustering the publications in a citation network, we present a systematic comparison of the performance of a large number of these clustering methods. Using a number of different citation networks, some of them relatively small and others very large, we extensively study the statistical properties of the results provided by different methods. In addition, we also carry out an expert-based assessment of the results produced by different methods. The expert-based assessment focuses on publications in the field of scientometrics. Our findings seem to indicate that there is a trade-off between different properties that may be considered desirable for a good clustering of publications. Overall, map equation methods appear to perform best in our analysis, suggesting that these methods deserve more attention from the bibliometric community.

Uncovering disease mechanisms through network biology in the era of Next Generation Sequencing

Characterizing the behavior of disease genes in the context of biological networks has the potential to shed light on disease mechanisms, and to reveal both new candidate disease genes and therapeutic targets. Previous studies addressing the network properties of disease genes have produced contradictory results. Here we have explored the causes of these discrepancies and assessed the relationship between the network roles of disease genes and their tolerance to deleterious germline variants in human populations leveraging on: the abundance of interactome resources, a comprehensive catalog of disease genes and exome variation data. We found that the most salient network features of disease genes are driven by cancer genes and that genes related to different types of diseases play network roles whose centrality is inversely correlated to their tolerance to likely deleterious germline mutations. This proved to be a multiscale signature, including global, mesoscopic and local network centrality features. Cancer driver genes, the most sensitive to deleterious variants, occupy the most central positions, followed by dominant disease genes and then by recessive disease genes, which are tolerant to variants and isolated within their network modules.

Overlapping Community Detection based on Network Decomposition

Community detection in complex network has become a vital step to understand the structure and dynamics of networks in various fields. However, traditional node clustering and relatively new proposed link clustering methods have inherent drawbacks to discover overlapping communities. Node clustering is inadequate to capture the pervasive overlaps, while link clustering is often criticized due to the high computational cost and ambiguous definition of communities. So, overlapping community detection is still a formidable challenge. In this work, we propose a new overlapping community detection algorithm based on network decomposition, called NDOCD. Specifically, NDOCD iteratively splits the network by removing all links in derived link communities, which are identified by utilizing node clustering technique. The network decomposition contributes to reducing the computation time and noise link elimination conduces to improving the quality of obtained communities. Besides, we employ node clustering technique rather than link similarity measure to discover link communities, thus NDOCD avoids an ambiguous definition of community and becomes less time-consuming. We test our approach on both synthetic and real-world networks. Results demonstrate the superior performance of our approach both in computation time and accuracy compared to state-of-the-art algorithms.

Behavior Based Social Dimensions Extraction for Multi-Label Classification

Classification based on social dimensions is commonly used to handle the multi-label classification task in heterogeneous networks. However, traditional methods, which mostly rely on the community detection algorithms to extract the latent social dimensions, produce unsatisfactory performance when community detection algorithms fail. In this paper, we propose a novel behavior based social dimensions extraction method to improve the classification performance in multi-label heterogeneous networks. In our method, nodes’ behavior features, instead of community memberships, are used to extract social dimensions. By introducing Latent Dirichlet Allocation (LDA) to model the network generation process, nodes’ connection behaviors with different communities can be extracted accurately, which are applied as latent social dimensions for classification. Experiments on various public datasets reveal that the proposed method can obtain satisfactory classification results in comparison to other state-of-the-art methods on smaller social dimensions.

Inference and Analysis of Population Structure Using Genetic Data and Network Theory

Clustering individuals to subpopulations based on genetic data has become commonplace in many genetic studies. Inference about population structure is most often done by applying model-based approaches, aided by visualization using distance-based approaches such as multidimensional scaling. While existing distance-based approaches suffer from a lack of statistical rigor, model-based approaches entail assumptions of prior conditions such as that the subpopulations are at Hardy-Weinberg equilibria. Here we present a distance-based approach for inference about population structure using genetic data by defining population structure using network theory terminology and methods. A network is constructed from a pairwise genetic-similarity matrix of all sampled individuals. The community partition, a partition of a network to dense subgraphs, is equated with population structure, a partition of the population to genetically related groups. Community-detection algorithms are used to partition the network into communities, interpreted as a partition of the population to subpopulations. The statistical significance of the structure can be estimated by using permutation tests to evaluate the significance of the partition's modularity, a network theory measure indicating the quality of community partitions. To further characterize population structure, a new measure of the strength of association (SA) for an individual to its assigned community is presented. The strength of association distribution (SAD) of the communities is analyzed to provide additional population structure characteristics, such as the relative amount of gene flow experienced by the different subpopulations and identification of hybrid individuals. Human genetic data and simulations are used to demonstrate the applicability of the analyses. The approach presented here provides a novel, computationally efficient model-free method for inference about population structure that does not entail assumption of prior conditions. The method is implemented in the software NetStruct (available at https://giligreenbaum.wordpress.com/software/).

Efficient community detection of network flows for varying Markov times and bipartite networks

Community detection of network flows conventionally assumes one-step dynamics on the links. For sparse networks and interest in large-scale structures, longer timescales may be more appropriate. Oppositely, for large networks and interest in small-scale structures, shorter timescales may be better. However, current methods for analyzing networks at different timescales require expensive and often infeasible network reconstructions. To overcome this problem, we introduce a method that takes advantage of the inner workings of the map equation and evades the reconstruction step. This makes it possible to efficiently analyze large networks at different Markov times with no extra overhead cost. The method also evades the costly unipartite projection for identifying flow modules in bipartite networks.

Comparing Alzheimer's and Parkinson's diseases networks using graph communities structure

BACKGROUND

Recent advances in large datasets analysis offer new insights to modern biology allowing system-level investigation of pathologies. Here we describe a novel computational method that exploits the ever-growing amount of "omics" data to shed light on Alzheimer's and Parkinson's diseases. Neurological disorders exhibit a huge number of molecular alterations due to a complex interplay between genetic and environmental factors. Classical reductionist approaches are focused on a few elements, providing a narrow overview of the etiopathogenic complexity of multifactorial diseases. On the other hand, high-throughput technologies allow the evaluation of many components of biological systems and their behaviors. Analysis of Parkinson's Disease (PD) and Alzheimer's Disease (AD) from a network perspective can highlight proteins or pathways common but differently represented that can be discriminating between the two pathological conditions, thus highlight similarities and differences.

RESULTS

In this work we propose a strategy that exploits network community structure identified with a state-of-the-art network community discovery algorithm called InfoMap, which takes advantage of information theory principles. We used two similarity measurements to quantify functional and topological similarities between the two pathologies. We built a Similarity Matrix to highlight similar communities and we analyzed statistically significant GO terms found in clustered areas of the matrix and in network communities. Our strategy allowed us to identify common known and unknown processes including DNA repair, RNA metabolism and glucose metabolism not detected with simple GO enrichment analysis. In particular, we were able to capture the connection between mitochondrial dysfunction and metabolism (glucose and glutamate/glutamine).

CONCLUSIONS

This approach allows the identification of communities present in both pathologies which highlight common biological processes. Conversely, the identification of communities without any counterpart can be used to investigate processes that are characteristic of only one of the two pathologies. In general, the same strategy can be applied to compare any pair of biological networks.

Contagion processes on the static and activity-driven coupling networks

The evolution of network structure and the spreading of epidemic are common coexistent dynamical processes. In most cases, network structure is treated as either static or time-varying, supposing the whole network is observed in the same time window. In this paper, we consider the epidemics spreading on a network which has both static and time-varying structures. Meanwhile, the time-varying part and the epidemic spreading are supposed to be of the same time scale. We introduce a static and activity-driven coupling (SADC) network model to characterize the coupling between the static ("strong") structure and the dynamic ("weak") structure. Epidemic thresholds of the SIS and SIR models are studied using the SADC model both analytically and numerically under various coupling strategies, where the strong structure is of homogeneous or heterogeneous degree distribution. Theoretical thresholds obtained from the SADC model can both recover and generalize the classical results in static and time-varying networks. It is demonstrated that a weak structure might make the epidemic threshold low in homogeneous networks but high in heterogeneous cases. Furthermore, we show that the weak structure has a substantive effect on the outbreak of the epidemics. This result might be useful in designing some efficient control strategies for epidemics spreading in networks.

Cell Assembly Dynamics of Sparsely-Connected Inhibitory Networks: A Simple Model for the Collective Activity of Striatal Projection Neurons

Striatal projection neurons form a sparsely-connected inhibitory network, and this arrangement may be essential for the appropriate temporal organization of behavior. Here we show that a simplified, sparse inhibitory network of Leaky-Integrate-and-Fire neurons can reproduce some key features of striatal population activity, as observed in brain slices. In particular we develop a new metric to determine the conditions under which sparse inhibitory networks form anti-correlated cell assemblies with time-varying activity of individual cells. We find that under these conditions the network displays an input-specific sequence of cell assembly switching, that effectively discriminates similar inputs. Our results support the proposal that GABAergic connections between striatal projection neurons allow stimulus-selective, temporally-extended sequential activation of cell assemblies. Furthermore, we help to show how altered intrastriatal GABAergic signaling may produce aberrant network-level information processing in disorders such as Parkinson's and Huntington's diseases.

Exploring the topological sources of robustness against invasion in biological and technological networks

For a network, the accomplishment of its functions despite perturbations is called robustness. Although this property has been extensively studied, in most cases, the network is modified by removing nodes. In our approach, it is no longer perturbed by site percolation, but evolves after site invasion. The process transforming resident/healthy nodes into invader/mutant/diseased nodes is described by the Moran model. We explore the sources of robustness (or its counterpart, the propensity to spread favourable innovations) of the US high-voltage power grid network, the Internet2 academic network, and the C. elegans connectome. We compare them to three modular and non-modular benchmark networks, and samples of one thousand random networks with the same degree distribution. It is found that, contrary to what happens with networks of small order, fixation probability and robustness are poorly correlated with most of standard statistics, but they depend strongly on the degree distribution. While community detection techniques are able to detect the existence of a central core in Internet2, they are not effective in detecting hierarchical structures whose topological complexity arises from the repetition of a few rules. Box counting dimension and Rent’s rule are applied to show a subtle trade-off between topological and wiring complexity.

Comparison of social structures within cities of very different sizes

People make a city, making each city as unique as the combination of its inhabitants. However, some cities are similar and some cities are inimitable. We examine the social structure of 10 different cities using Twitter data. Each city is decomposed to its communities. We show that in many cases one city can be thought of as an amalgamation of communities from another city. For example, we find the social network of Manchester is very similar to the social network of a virtual city of the same size, where the virtual city is composed of communities from the Bristol network. However, we cannot create Bristol from Manchester since Bristol contains communities with a social structure that are not present in Manchester. Some cities, such as Leeds, are outliers. That is, Leeds contains a particularly wide range of communities, meaning we cannot build a similar city from communities outside of Leeds. Comparing communities from different cities, and building virtual cities that are comparable to real cities, is a novel approach to understand social networks. This has implications when using social media to inform or advise residents of a city.

Z-Score-Based Modularity for Community Detection in Networks

Identifying community structure in networks is an issue of particular interest in network science. The modularity introduced by Newman and Girvan is the most popular quality function for community detection in networks. In this study, we identify a problem in the concept of modularity and suggest a solution to overcome this problem. Specifically, we obtain a new quality function for community detection. We refer to the function as Z-modularity because it measures the Z-score of a given partition with respect to the fraction of the number of edges within communities. Our theoretical analysis shows that Z-modularity mitigates the resolution limit of the original modularity in certain cases. Computational experiments using both artificial networks and well-known real-world networks demonstrate the validity and reliability of the proposed quality function.

Modular structure of brain functional networks: breaking the resolution limit by Surprise

The modular organization of brain networks has been widely investigated using graph theoretical approaches. Recently, it has been demonstrated that graph partitioning methods based on the maximization of global fitness functions, like Newman's Modularity, suffer from a resolution limit, as they fail to detect modules that are smaller than a scale determined by the size of the entire network. Here we explore the effects of this limitation on the study of brain connectivity networks. We demonstrate that the resolution limit prevents detection of important details of the brain modular structure, thus hampering the ability to appreciate differences between networks and to assess the topological roles of nodes. We show that Surprise, a recently proposed fitness function based on probability theory, does not suffer from these limitations. Surprise maximization in brain co-activation and functional connectivity resting state networks reveals the presence of a rich structure of heterogeneously distributed modules, and differences in networks' partitions that are undetectable by resolution-limited methods. Moreover, Surprise leads to a more accurate identification of the network's connector hubs, the elements that integrate the brain modules into a cohesive structure.

Network-Based Analysis for Uncovering Mechanisms Underlying Alzheimer's Disease

Alzheimer's disease (AD) is known to be a multifactorial neurodegenerative disorder, and is one of the main causes of dementia in the elderly. Many studies have demonstrated molecules involved in the pathogenesis of AD, however its underlying mechanisms remain obscure. It may be simplistic to try to explain the disease based on the role of a few genes only. Accumulating new, huge amount of information from e.g. genome, proteome and interactome datasets and new knowledge, we are now able to clarify and characterize diseases essentially as a result of dysfunction of molecular networks. Recent studies have indicated that relevant genes affected in human diseases concentrate in a part of the network, often called as "disease module." In the case of AD, some disease-associated pathways seem different, but some of them are clearly disease-related and coherent. This suggests the existence of a common pathway that negatively drives from healthy state to disease state (i.e., the disease module(s)). Additionally, such disease modules should dynamically change through AD progression. Thus, network-level approaches are indispensable to address unknown mechanisms of AD. In this chapter, we introduce network strategies using gene co-expression and protein interaction networks.