Community detection algorithms: a comparative analysis

Reliable Link Inference for Network Data With Community Structures

Complex systems are often characterized by complex networks with links and entities. However, in many complex systems such as protein-protein interaction networks, recommender systems, and online communities, their links are hard to reveal directly, but they can be inaccurately observed by multiple data collection platforms or by a data collection platform at different times. Then, the links of the systems are inferred by the integration of the collected observations. As those data collection platforms are usually distributed over a large area and in different fields, their observations are unreliable and sensitive to the potential structures of the systems. In this paper, we consider the link inference problem in network data with community structures, in which the reliability of data collection platforms is unknown a priori and the link errors and reliability of platforms' observations are heterogeneous to the underlying community structures of the systems. We propose an expectation maximization algorithm for link inference in a network system with community structures (EMLIC). The EMLIC algorithm is also used to infer the link errors and reliability of platforms' observations in different communities. Experimental results on both synthetic data and eight real-world network data demonstrate that our algorithm is able to achieve lower link errors than the existing reliable link inference algorithms when the network data have community structures.

Challenges in unsupervised clustering of single-cell RNA-seq data

Single-cell RNA sequencing (scRNA-seq) allows researchers to collect large catalogues detailing the transcriptomes of individual cells. Unsupervised clustering is of central importance for the analysis of these data, as it is used to identify putative cell types. However, there are many challenges involved. We discuss why clustering is a challenging problem from a computational point of view and what aspects of the data make it challenging. We also consider the difficulties related to the biological interpretation and annotation of the identified clusters.

InfoFlow: A Distributed Algorithm to Detect Communities According to the Map Equation

Formidably sized networks are becoming more and more common, including in social sciences, biology, neuroscience, and the technology space. Many network sizes are expected to challenge the storage capability of a single physical computer. Here, we take two approaches to handle big networks: first, we look at how big data technology and distributed computing is an exciting approach to big data storage and processing. Second, most networks can be partitioned or labeled into communities, clusters, or modules, thus capturing the crux of the network while reducing detailed information, through the class of algorithms known as community detection. In this paper, we combine these two approaches, developing a distributed community detection algorithm to handle big networks. In particular, the map equation provides a way to identify network communities according to the information flow between nodes, where InfoMap is a greedy algorithm that uses the map equation. We develop discrete mathematics to adapt InfoMap into a distributed computing framework and then further develop the mathematics for a greedy algorithm, InfoFlow, which has logarithmic time complexity, compared to the linear complexity in InfoMap. Benchmark results of graphs up to millions of nodes and hundreds of millions of edges confirm the time complexity improvement, while maintaining community accuracy. Thus, we develop a map equation based community detection algorithm suitable for big network data processing.

Perception, prestige and PageRank

Academic prestige is difficult to quantify in objective terms. Network theory offers the opportunity to use a mathematical formalism to model both the prestige associated with an academic and the relationships between academic colleagues. Early attempts using this line of reasoning have focused on intellectual genealogy as constituted by supervisor student networks. The process of examination is critical in many areas of study but has not played a part in existing models. A network theoretical "social" model is proposed as a tool to explore and understand the dynamics of prestige in the academic hierarchy. It is observed that such a model naturally gives rise to the idea that the prestige associated with a node in the graph (the prestige of an individual academic) can be viewed as a dynamic quantity that evolves with time based on both local and non-local changes in the properties in the network. The toy model studied here includes both supervisor-student and examiner-student relationships. This gives an insight into some of the key features of academic genealogies and naturally leads to a proposed model for "prestige propagation" on academic networks. This propagation is not solely directed forward in time (from teacher to progeny) but sometimes also flows in the other direction. As collaborators do well, this reflects well on those with whom they choose to collaborate and those that taught them. Furthermore, prestige as a quantity continues to be dynamic even after the end of a relationship or career. Given that time ordering of relationships on the network are implicit but that measures such as betweenness are independent of this implicit time dependence: the success of a PhD student later in their career can improve the prestige of their doctoral supervisor. Thus, prestige can be interpreted to have dynamics that flow both forward and backward in time.

A SOM-Based Membrane Optimization Algorithm for Community Detection

The real world is full of rich and valuable complex networks. Community structure is an important feature in complex networks, which makes possible the discovery of some structure or hidden related information for an in-depth study of complex network structures and functional characteristics. Aimed at community detection in complex networks, this paper proposed a membrane algorithm based on a self-organizing map (SOM) network. Firstly, community detection was transformed as discrete optimization problems by selecting the optimization function. Secondly, three elements of the membrane algorithm, objects, reaction rules, and membrane structure were designed to analyze the properties and characteristics of the community structure. Thirdly, a SOM was employed to determine the number of membranes by learning and mining the structure of the current objects in the decision space, which is beneficial to guiding the local and global search of the proposed algorithm by constructing the neighborhood relationship. Finally, the simulation experiment was carried out on both synthetic benchmark networks and four real-world networks. The experiment proved that the proposed algorithm had higher accuracy, stability, and execution efficiency, compared with the results of other experimental algorithms.

Effects of Brain Parcellation on the Characterization of Topological Deterioration in Alzheimer's Disease

Alzheimer's disease (AD) causes the progressive deterioration of neural connections, disrupting structural connectivity (SC) networks within the brain. Graph-based analyses of SC networks have shown that topological properties can reveal the course of AD propagation. Different whole-brain parcellation schemes have been developed to define the nodes of these SC networks, although it remains unclear which scheme can best describe the AD-related deterioration of SC networks. In this study, four whole-brain parcellation schemes with different numbers of parcels were used to define SC network nodes. SC networks were constructed based on high angular resolution diffusion imaging (HARDI) tractography for a mixed cohort that includes 20 normal controls (NC), 20 early mild cognitive impairment (EMCI), 20 late mild cognitive impairment (LMCI), and 20 AD patients, from the Alzheimer's Disease Neuroimaging Initiative. Parcellation schemes investigated in this study include the OASIS-TRT-20 (62 regions), AAL (116 regions), HCP-MMP (180 regions), and Gordon-rsfMRI (333 regions), which have all been widely used for the construction of brain structural or functional connectivity networks. Topological characteristics of the SC networks, including the network strength, global efficiency, clustering coefficient, rich-club, characteristic path length, k-core, rich-club coefficient, and modularity, were fully investigated at the network level. Statistical analyses were performed on these metrics using Kruskal-Wallis tests to examine the group differences that were apparent at different stages of AD progression. Results suggest that the HCP-MMP scheme is the most robust and sensitive to AD progression, while the OASIS-TRT-20 scheme is sensitive to group differences in network strength, global efficiency, k-core, and rich-club coefficient at k-levels from 18 and 39. With the exception of the rich-club and modularity coefficients, AAL could not significantly identify group differences on other topological metrics. Further, the Gordon-rsfMRI atlas only significantly differentiates the groups on network strength, characteristic path length, k-core, and rich-club coefficient. Results show that the topological examination of SC networks with different parcellation schemes can provide important complementary AD-related information and thus contribute to a more accurate and earlier diagnosis of AD.

Stochastic block models: A comparison of variants and inference methods

Finding communities in complex networks is a challenging task and one promising approach is the Stochastic Block Model (SBM). But the influences from various fields led to a diversity of variants and inference methods. Therefore, a comparison of the existing techniques and an independent analysis of their capabilities and weaknesses is needed. As a first step, we review the development of different SBM variants such as the degree-corrected SBM of Karrer and Newman or Peixoto's hierarchical SBM. Beside stating all these variants in a uniform notation, we show the reasons for their development. Knowing the variants, we discuss a variety of approaches to infer the optimal partition like the Metropolis-Hastings algorithm. We perform our analysis based on our extension of the Girvan-Newman test and the Lancichinetti-Fortunato-Radicchi benchmark as well as a selection of some real world networks. Using these results, we give some guidance to the challenging task of selecting an inference method and SBM variant. In addition, we give a simple heuristic to determine the number of steps for the Metropolis-Hastings algorithms that lack a usual stop criterion. With our comparison, we hope to guide researches in the field of SBM and highlight the problem of existing techniques to focus future research. Finally, by making our code freely available, we want to promote a faster development, integration and exchange of new ideas.

Gene regulatory networks on transfer entropy (GRNTE): a novel approach to reconstruct gene regulatory interactions applied to a case study for the plant pathogen Phytophthora infestans

Background

The increasing amounts of genomics data have helped in the understanding of the molecular dynamics of complex systems such as plant and animal diseases. However, transcriptional regulation, although playing a central role in the decision-making process of cellular systems, is still poorly understood. In this study, we linked expression data with mathematical models to infer gene regulatory networks (GRN). We present a simple yet effective method to estimate transcription factors’ GRNs from transcriptional data.

Method

We defined interactions between pairs of genes (edges in the GRN) as the partial mutual information between these genes that takes into account time and possible lags in time from one gene in relation to another. We call this method Gene Regulatory Networks on Transfer Entropy (GRNTE) and it corresponds to Granger causality for Gaussian variables in an autoregressive model. To evaluate the reconstruction accuracy of our method, we generated several sub-networks from the GRN of the eukaryotic yeast model, Saccharomyces cerevisae. Then, we applied this method using experimental data of the plant pathogen Phytophthora infestans. We evaluated the transcriptional expression levels of 48 transcription factors of P. infestans during its interaction with one moderately resistant and one susceptible cultivar of yellow potato (Solanum tuberosum group Phureja), using RT-qPCR. With these data, we reconstructed the regulatory network of P. infestans during its interaction with these hosts.

Results

We first evaluated the performance of our method, based on the transfer entropy (GRNTE), on eukaryotic datasets from the GRNs of the yeast S. cerevisae. Results suggest that GRNTE is comparable with the state-of-the-art methods when the parameters for edge detection are properly tuned. In the case of P. infestans, most of the genes considered in this study, showed a significant change in expression from the onset of the interaction (0 h post inoculum - hpi) to the later time-points post inoculation. Hierarchical clustering of the expression data discriminated two distinct periods during the infection: from 12 to 36 hpi and from 48 to 72 hpi for both the moderately resistant and susceptible cultivars. These distinct periods could be associated with two phases of the life cycle of the pathogen when infecting the host plant: the biotrophic and necrotrophic phases.

Conclusions

Here we presented an algorithmic solution to the problem of network reconstruction in time series data. This analytical perspective makes use of the dynamic nature of time series data as it relates to intrinsically dynamic processes such as transcription regulation, were multiple elements of the cell (e.g., transcription factors) act simultaneously and change over time. We applied the algorithm to study the regulatory network of P. infestans during its interaction with two hosts which differ in their level of resistance to the pathogen. Although the gene expression analysis did not show differences between the two hosts, the results of the GRN analyses evidenced rewiring of the genes’ interactions according to the resistance level of the host. This suggests that different regulatory processes are activated in response to different environmental cues. Applications of our methodology showed that it could reliably predict where to place edges in the transcriptional networks and sub-networks. The experimental approach used here can help provide insights on the biological role of these interactions on complex processes such as pathogenicity. The code used is available at https://github.com/jccastrog/GRNTE under GNU general public license 3.0.

Electronic supplementary material

The online version of this article (10.1186/s12976-019-0103-7) contains supplementary material, which is available to authorized users.

Fast consensus clustering in complex networks

Algorithms for community detection are usually stochastic, leading to different partitions for different choices of random seeds. Consensus clustering has proven to be an effective technique to derive more stable and accurate partitions than the ones obtained by the direct application of the algorithm. However, the procedure requires the calculation of the consensus matrix, which can be quite dense if (some of) the clusters of the input partitions are large. Consequently, the complexity can get dangerously close to quadratic, which makes the technique inapplicable on large graphs. Here, we present a fast variant of consensus clustering, which calculates the consensus matrix only on the links of the original graph and on a comparable number of additional node pairs, suitably chosen. This brings the complexity down to linear, while the performance remains comparable as the full technique. Therefore, our fast consensus clustering procedure can be applied on networks with millions of nodes and links.

Research on the Complex Characteristics of Freight Transportation from a Multiscale Perspective Using Freight Vehicle Trip Data

To better guide the sustainable developing of freight transport aligning with environmental objectives it is of strategic importance to capture freight transportation characteristics more realistically. This paper characterizes freight transportation by using a complex network approach from multidimensional perspectives based on freight vehicle trips data. We first build two subnetworks from prefecture-level city-scale and county-level city-scale. Subsequently, network analysis indices based on complex network theory were applied to examine the topological structure and complexity of the freight transportation networks. Furthermore, the community detection method is introduced to reveal the networks’ clustering characteristics. The findings show that the prefecture-level city-scale network and the county-level city-scale network both have obvious small-world network characteristics, but the prefecture-level city-scale network has higher operating efficiency for goods movement. Additionally, the influence of the cross-border effect on the freight transportation network was verified. In terms of the community structure, the freight network shows distinct clustering features only at the county-level city-scale.

From Louvain to Leiden: guaranteeing well-connected communities

Community detection is often used to understand the structure of large and complex networks. One of the most popular algorithms for uncovering community structure is the so-called Louvain algorithm. We show that this algorithm has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively. In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected. To address this problem, we introduce the Leiden algorithm. We prove that the Leiden algorithm yields communities that are guaranteed to be connected. In addition, we prove that, when the Leiden algorithm is applied iteratively, it converges to a partition in which all subsets of all communities are locally optimally assigned. Furthermore, by relying on a fast local move approach, the Leiden algorithm runs faster than the Louvain algorithm. We demonstrate the performance of the Leiden algorithm for several benchmark and real-world networks. We find that the Leiden algorithm is faster than the Louvain algorithm and uncovers better partitions, in addition to providing explicit guarantees.

Survey of local and global biological network alignment: the need to reconcile the two sides of the same coin

Analogous to genomic sequence alignment that allows for across-species transfer of biological knowledge between conserved sequence regions, biological network alignment can be used to guide the knowledge transfer between conserved regions of molecular networks of different species. Hence, biological network alignment can be used to redefine the traditional notion of a sequence-based homology to a new notion of network-based homology. Analogous to genomic sequence alignment, there exist local and global biological network alignments. Here, we survey prominent and recent computational approaches of each network alignment type and discuss their (dis)advantages. Then, as it was recently shown that the two approach types are complementary, in the sense that they capture different slices of cellular functioning, we discuss the need to reconcile the two network alignment types and present a recent first step in this direction. We conclude with some open research problems on this topic and comment on the usefulness of network alignment in other domains besides computational biology.

Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection

Modularity maximization using greedy algorithms continues to be a popular approach toward community detection in graphs, even after various better forming algorithms have been proposed. Apart from its clear mechanism and ease of implementation, this approach is persistently popular because, presumably, its risk of algorithmic failure is not well understood. This Rapid Communication provides insight into this issue by estimating the algorithmic performance limit of the stochastic block model inference using modularity maximization. This is achieved by counting the number of metastable states under a local update rule. Our results offer a quantitative insight into the level of sparsity at which a greedy algorithm typically fails.

The cingulum as a marker of individual differences in neurocognitive development

The canonical approach to exploring brain-behaviour relationships is to group individuals according to a phenotype of interest, and then explore the neural correlates of this grouping. A limitation of this approach is that multiple aetiological pathways could result in a similar phenotype, so the role of any one brain mechanism may be substantially underestimated. Building on advances in network analysis, we used a data-driven community-clustering algorithm to identify robust subgroups based on white-matter microstructure in childhood and adolescence (total N = 313, mean age: 11.24 years). The algorithm indicated the presence of two equal-size groups that show a critical difference in fractional anisotropy (FA) of the left and right cingulum. Applying the brain-based grouping in independent samples, we find that these different 'brain types' had profoundly different cognitive abilities with higher performance in the higher FA group. Further, a connectomics analysis indicated reduced structural connectivity in the low FA subgroup that was strongly related to reduced functional activation of the default mode network. These results provide a proof-of-concept that bottom-up brain-based groupings can be identified that relate to cognitive performance. This provides a first demonstration of a complimentary approach for investigating individual differences in brain structure and function, particularly for neurodevelopmental disorders where researchers are often faced with phenotypes that are difficult to define at the cognitive or behavioural level.

Functional homogeneity and specificity of topological modules in human proteome

BACKGROUND

Functional modules in protein-protein interaction networks (PPIN) are defined by maximal sets of functionally associated proteins and are vital to understanding cellular mechanisms and identifying disease associated proteins. Topological modules of the human proteome have been shown to be related to functional modules of PPIN. However, the effects of the weights of interactions between protein pairs and the integration of physical (direct) interactions with functional (indirect expression-based) interactions have not been investigated in the detection of functional modules of the human proteome.

RESULTS

We investigated functional homogeneity and specificity of topological modules of the human proteome and validated them with known biological and disease pathways. Specifically, we determined the effects on functional homogeneity and heterogeneity of topological modules (i) with both physical and functional protein-protein interactions; and (ii) with incorporation of functional similarities between proteins as weights of interactions. With functional enrichment analyses and a novel measure for functional specificity, we evaluated functional relevance and specificity of topological modules of the human proteome.

CONCLUSIONS

The topological modules ranked using specificity scores show high enrichment with gene sets of known functions. Physical interactions in PPIN contribute to high specificity of the topological modules of the human proteome whereas functional interactions contribute to high homogeneity of the modules. Weighted networks result in more number of topological modules but did not affect their functional propensity. Modules of human proteome are more homogeneous for molecular functions than biological processes.

Network-based microsynteny analysis identifies major differences and genomic outliers in mammalian and angiosperm genomes

Studying the organization of genes within genomes across broad evolutionary timescales can advance our understanding of the evolution of traits and clades. We have used a network approach to investigate genome dynamics of mammals and angiosperms. In general, genome organization and gene microcollinearity is much more conserved in mammals than in flowering plants. We then identified the genomic outliers or “rebel genes,” within each clade. Genes that have moved are unusual for mammals, whereas highly conserved single-copy genes are exceptional for plants. How conservation and changes in synteny or fundamental differences in genome organization have contributed to the evolution of lineages could be a new scientific frontier.

A comprehensive analysis of relative gene order, or microsynteny, can provide valuable information for understanding the evolutionary history of genes and genomes, and ultimately traits and species, across broad phylogenetic groups and divergence times. We have used our network-based phylogenomic synteny analysis pipeline to first analyze the overall patterns and major differences between 87 mammalian and 107 angiosperm genomes. These two important groups have both evolved and radiated over the last ∼170 MYR. Secondly, we identified the genomic outliers or “rebel genes” within each clade. We theorize that rebel genes potentially have influenced trait and lineage evolution. Microsynteny networks use genes as nodes and syntenic relationships between genes as edges. Networks were decomposed into clusters using the Infomap algorithm, followed by phylogenomic copy-number profiling of each cluster. The differences in syntenic properties of all annotated gene families, including BUSCO genes, between the two clades are striking: most genes are single copy and syntenic across mammalian genomes, whereas most genes are multicopy and/or have lineage-specific distributions for angiosperms. We propose microsynteny scores as an alternative and complementary metric to BUSCO for assessing genome assemblies. We further found that the rebel genes are different between the two groups: lineage-specific gene transpositions are unusual in mammals, whereas single-copy highly syntenic genes are rare for flowering plants. We illustrate several examples of mammalian transpositions, such as brain-development genes in primates, and syntenic conservation across angiosperms, such as single-copy genes related to photosynthesis. Future experimental work can test if these are indeed rebels with a cause.

Function Analysis of Human Protein Interactions Based on a Novel Minimal Loop Algorithm

Background:

Various properties of Protein-Protein Interaction (PPI) network have been widely exploited to discover the topological organizing principle and the crucial function motifs involving specific biological pathway or disease process. The current motifs of PPI network are either detected by the topology-based coarse grain algorithms, i.e. community discovering, or depended on the limited-accessible protein annotation data derived precise algorithms. However, the identified network motifs are hardly compatible with the well-defined biological functions according to those two types of methods.

Method:

In this paper, we proposed a minimal protein loop finding method to explore the elementary structural motifs of human PPI network. Initially, an improved article exchange model was designed to search all the independent shortest protein loops of PPI network. Furthermore, Gene Ontology (GO) based function clustering analysis was implemented to identify the biological functions of the shortest protein loops. Additionally, the disease process associated shortest protein loops were considered as the potential drug targets. </P><P> Result: Our proposed method presents the lowest computational complexity and the highest functional consistency, compared to the three other methods. The functional enrichment and clustering analysis for the identified minimal protein loops revealed the high correlation between the protein loops and the corresponding biological functions, particularly, statistical analysis presenting the protein loops with the length less than 4 is closely connected with some disease process, suggesting the potential drug target.

Conclusion:

Our minimal protein loop method provides a novel manner to precisely define the functional motif of PPI network, which extends the current knowledge about the cooperating mechanisms and topological properties of protein modules composed of the short loops.

Identification of Cell Types from Single-Cell Transcriptomic Data

Unprecedented technological advances in single-cell RNA-sequencing (scRNA-seq) technology have now made it possible to profile genome-wide expression in single cells at low cost and high throughput. There is substantial ongoing effort to use scRNA-seq measurements to identify the "cell types" that form components of a complex tissue, akin to taxonomizing species in ecology. Cell type classification from scRNA-seq data involves the application of computational tools rooted in dimensionality reduction and clustering, and statistical analysis to identify molecular signatures that are unique to each type. As datasets continue to grow in size and complexity, computational challenges abound, requiring analytical methods to be scalable, flexible, and robust. Moreover, careful consideration needs to be paid to experimental biases and statistical challenges that are unique to these measurements to avoid artifacts. This chapter introduces these topics in the context of cell-type identification, and outlines an instructive step-by-step example bioinformatic pipeline for researchers entering this field.

Comparison of Methods to Identify Modules in Noisy or Incomplete Brain Networks

Community structure, or "modularity," is a fundamentally important aspect in the organization of structural and functional brain networks, but their identification with community detection methods is confounded by noisy or missing connections. Although several methods have been used to account for missing data, the performance of these methods has not been compared quantitatively so far. In this study, we compared four different approaches to account for missing connections when identifying modules in binary and weighted networks using both Louvain and Infomap community detection algorithms. The four methods are "zeros," "row-column mean," "common neighbors," and "consensus clustering." Using Lancichinetti-Fortunato-Radicchi benchmark-simulated binary and weighted networks, we find that "zeros," "row-column mean," and "common neighbors" approaches perform well with both Louvain and Infomap, whereas "consensus clustering" performs well with Louvain but not Infomap. A similar pattern of results was observed with empirical networks from stereotactical electroencephalography data, except that "consensus clustering" outperforms other approaches on weighted networks with Louvain. Based on these results, we recommend any of the four methods when using Louvain on binary networks, whereas "consensus clustering" is superior with Louvain clustering of weighted networks. When using Infomap, "zeros" or "common neighbors" should be used for both binary and weighted networks. These findings provide a basis to accounting for noisy or missing connections when identifying modules in brain networks.

Influence spreading model used to analyse social networks and detect sub-communities

A dynamic influence spreading model is presented for computing network centrality and betweenness measures. Network topology, and possible directed connections and unequal weights of nodes and links, are essential features of the model. The same influence spreading model is used for community detection in social networks and for analysis of network structures. Weaker connections give rise to more sub-communities whereas stronger ties increase the cohesion of a community. The validity of the method is demonstrated with different social networks. Our model takes into account different paths between nodes in the network structure. The dependency of different paths having common links at the beginning of their paths makes the model more realistic compared to classical structural, simulation and random walk models. The influence of all nodes in a network has not been satisfactorily understood. Existing models may underestimate the spreading power of interconnected peripheral nodes as initiators of dynamic processes in social, biological and technical networks.

Disentangling the evolution of MEDLINE bibliographic database: A complex network perspective

Scientific knowledge constitutes a complex system that has recently been the topic of in-depth analysis. Empirical evidence reveals that little is known about the dynamic aspects of human knowledge. Precise dissection of the expansion of scientific knowledge could help us to better understand the evolutionary dynamics of science. In this paper, we analyzed the dynamic properties and growth principles of the MEDLINE bibliographic database using network analysis methodology. The basic assumption of this work is that the scientific evolution of the life sciences can be represented as a list of co-occurrences of MeSH descriptors that are linked to MEDLINE citations. The MEDLINE database was summarized as a complex system, consisting of nodes and edges, where the nodes refer to knowledge concepts and the edges symbolize corresponding relations. We performed an extensive statistical evaluation based on more than 25 million citations in the MEDLINE database, from 1966 until 2014. We based our analysis on node and community level in order to track temporal evolution in the network. The degree distribution of the network follows a stretched exponential distribution which prevents the creation of large hubs. Results showed that the appearance of new MeSH terms does not also imply new connections. The majority of new connections among nodes results from old MeSH descriptors. We suggest a wiring mechanism based on the theory of structural holes, according to which a novel scientific discovery is established when a connection is built among two or more previously disconnected parts of scientific knowledge. Overall, we extracted 142 different evolving communities. It is evident that new communities are constantly born, live for some time, and then die. We also provide a Web-based application that helps characterize and understand the content of extracted communities. This study clearly shows that the evolution of MEDLINE knowledge correlates with the network's structural and temporal characteristics.

Online Social Networks (OSN) Evolution Model Based on Homophily and Preferential Attachment

In this paper, we propose a new scale-free social networks (SNs) evolution model that is based on homophily combined with preferential attachments. Our model enables the SN researchers to generate SN synthetic data for the evaluation of multi-facet SN models that are dependent on users’ attributes and similarities. Homophily is one of the key factors for interactive relationship formation in SN. The synthetic graph generated by our model is scale-invariant and has symmetric relationships. The model is dynamic and sustainable to changes in input parameters, such as number of nodes and nodes’ attributes, by conserving its structural properties. Simulation and evaluation of models for large-scale SN applications need large datasets. One way to get SN data is to generate synthetic data by using SN evolution models. Various SN evolution models are proposed to approximate the real-life SN graphs in previous research. These models are based on SN structural properties such as preferential attachment. The data generated by these models is suitable to evaluate SN models that are structure dependent but not suitable to evaluate models which depend on the SN users’ attributes and similarities. In our proposed model, users’ attributes and similarities are utilized to synthesize SN graphs. We evaluated the resultant synthetic graph by analyzing its structural properties. In addition, we validated our model by comparing its measures with the publicly available real-life SN datasets and previous SN evolution models. Simulation results show our resultant graph to be a close representation of real-life SN graphs with users’ attributes.

Does the Polycentric Urban Region Contribute to Economic Performance? The Case of Korea

This study aims to explore whether and to what extent two types of polycentricity, morphological and functional, affect the level of urban economic performance. In the analysis, it is found that morphological polycentricity is positively associated with the level of labor productivity whereas functional polycentricity is negatively related to it. In the context of the Korean urban system, characterized by the domination of a few cities and high levels of population density, regions which are more morphologically polycentric and functionally monocentric are likely to have higher labor productivity. These results reflect the processes of agglomeration economies and their impact on urban dynamics. This study contributes to the debates on the impacts of polycentricity on economic performance by examining this relationship in the East Asian context, not in Europe or America, and by distinguishing between effects of two types of polycentricity.

Microbial Interkingdom Interactions in Roots Promote Arabidopsis Survival

Roots of healthy plants are inhabited by soil-derived bacteria, fungi, and oomycetes that have evolved independently in distinct kingdoms of life. How these microorganisms interact and to what extent those interactions affect plant health are poorly understood. We examined root-associated microbial communities from three Arabidopsis thaliana populations and detected mostly negative correlations between bacteria and filamentous microbial eukaryotes. We established microbial culture collections for reconstitution experiments using germ-free A. thaliana. In plants inoculated with mono- or multi-kingdom synthetic microbial consortia, we observed a profound impact of the bacterial root microbiota on fungal and oomycetal community structure and diversity. We demonstrate that the bacterial microbiota is essential for plant survival and protection against root-derived filamentous eukaryotes. Deconvolution of 2,862 binary bacterial-fungal interactions ex situ, combined with community perturbation experiments in planta, indicate that biocontrol activity of bacterial root commensals is a redundant trait that maintains microbial interkingdom balance for plant health.

A Central Edge Selection Based Overlapping Community Detection Algorithm for the Detection of Overlapping Structures in Protein⁻Protein Interaction Networks

Overlapping structures of protein⁻protein interaction networks are very prevalent in different biological processes, which reflect the sharing mechanism to common functional components. The overlapping community detection (OCD) algorithm based on central node selection (CNS) is a traditional and acceptable algorithm for OCD in networks. The main content of CNS is the central node selection and the clustering procedure. However, the original CNS does not consider the influence among the nodes and the importance of the division of the edges in networks. In this paper, an OCD algorithm based on a central edge selection (CES) algorithm for detection of overlapping communities of protein⁻protein interaction (PPI) networks is proposed. Different from the traditional CNS algorithms for OCD, the proposed algorithm uses community magnetic interference (CMI) to obtain more reasonable central edges in the process of CES, and employs a new distance between the non-central edge and the set of the central edges to divide the non-central edge into the correct cluster during the clustering procedure. In addition, the proposed CES improves the strategy of overlapping nodes pruning (ONP) to make the division more precisely. The experimental results on three benchmark networks and three biological PPI networks of Mus. musculus, Escherichia coli, and Cerevisiae show that the CES algorithm performs well.

Changing characteristics of the empathic communication network after empathy-enhancement program for medical students

The Empathy-Enhancement Program for Medical Students (EEPMS) comprises five consecutive weekly sessions and aims to improve medical students' empathic ability, an essential component of humanistic medical professionalism. Using a graph theory approach for the Ising network (based on l1-regularized logistic regression) comprising emotional regulation, empathic understanding of others' emotion, and emotional expressivity, this study aimed to identify the central components or hubs of empathic communication and the changed profile of integration among these hubs after the EEPMS. Forty medical students participated in the EEPMS and completed the Depression Anxiety Stress Scale-21, the Empathy Quotient-Short Form, the Jefferson Scale of Empathy, and the Emotional Expressiveness Scale at baseline and after the EEPMS. The Ising model-based network of empathic communication was retrieved separately at two time points. Agitation, self-efficacy for predicting others' feelings, emotional concealment, active emotional expression, and emotional leakage ranked in the top 20% in terms of nodal strength and betweenness and closeness centralities, and they became hubs. After the EEPMS, the 'intentional emotional expressivity' component became less locally segregated (P = 0.014) and more directly integrated into those five hubs. This study shows how to quantitatively describe the qualitative item-level effects of the EEPMS. The key role of agitation in the network highlights the importance of stress management in preserving the capacity for empathic communication. The training effect of EEPMS, shown by the reduced local segregation and enhanced integration of 'intentional emotional expressivity' with hubs, suggests that the EEPMS could enable medical students to develop competency in emotional expression, which is an essential component of empathic communication.

A mechanistic model of connector hubs, modularity and cognition

The human brain network is modular-comprised of communities of tightly interconnected nodes1. This network contains local hubs, which have many connections within their own communities, and connector hubs, which have connections diversely distributed across communities2,3. A mechanistic understanding of these hubs and how they support cognition has not been demonstrated. Here, we leveraged individual differences in hub connectivity and cognition. We show that a model of hub connectivity accurately predicts the cognitive performance of 476 individuals in four distinct tasks. Moreover, there is a general optimal network structure for cognitive performance-individuals with diversely connected hubs and consequent modular brain networks exhibit increased cognitive performance, regardless of the task. Critically, we find evidence consistent with a mechanistic model in which connector hubs tune the connectivity of their neighbors to be more modular while allowing for task appropriate information integration across communities, which increases global modularity and cognitive performance.

Impact investing market on Twitter: influential users and communities

The 2008 financial crisis unveiled the intrinsic failures of the financial system as we know it. As a consequence, impact investing started to receive increasing attention, as evidenced by the high market growth rates. The goal of impact investment is to generate social and environmental impact alongside a financial return. In this paper we identify the main players in the sector and how they interact and communicate with each other. We use Twitter as a proxy of the impact investing market, and analyze relevant tweets posted over a period of ten months. We apply network, contents and sentiment analysis on the acquired dataset. Our study shows that Twitter users exhibit favourable leaning (predominantly neutral or positive) towards impact investing. Retweet communities are decentralised and include users from a variety of sectors. Despite some basic common vocabulary used by all retweet communities identified, the vocabulary and the topics discussed by each community vary largely. We note that an additional effort should be made in raising awareness about the sector, especially by policymakers and media outlets. The role of investors and the academia is also discussed, as well as the emergence of hybrid business models within the sector and its connections to the tech industry. This paper extends our previous study, one of the first analyses of Twitter activities in the impact investing market.

NeuroCave: A web-based immersive visualization platform for exploring connectome datasets

We introduce NeuroCave, a novel immersive visualization system that facilitates the visual inspection of structural and functional connectome datasets. The representation of the human connectome as a graph enables neuroscientists to apply network-theoretic approaches in order to explore its complex characteristics. With NeuroCave, brain researchers can interact with the connectome-either in a standard desktop environment or while wearing portable virtual reality headsets (such as Oculus Rift, Samsung Gear, or Google Daydream VR platforms)-in any coordinate system or topological space, as well as cluster brain regions into different modules on-demand. Furthermore, a default side-by-side layout enables simultaneous, synchronized manipulation in 3D, utilizing modern GPU hardware architecture, and facilitates comparison tasks across different subjects or diagnostic groups or longitudinally within the same subject. Visual clutter is mitigated using a state-of-the-art edge bundling technique and through an interactive layout strategy, while modular structure is optimally positioned in 3D exploiting mathematical properties of platonic solids. NeuroCave provides new functionality to support a range of analysis tasks not available in other visualization software platforms.

Social Networks and Health in a Prison Unit

Although a growing body of research documents lasting health consequences of incarceration, little is known about how confinement affects inmates' health while incarcerated. In this study, we examine the role of peer social integration and prisoners' self-reported health behaviors (smoking, exercise, perception of health, and depression) in a prison unit. We also consider whether inmates with similar health characteristics cluster within the unit. Drawing on a sample of 132 inmates in a "good behavior" unit, we leverage social network data to ask: In prison, is it healthier to become friends with other prisoners or keep your head down and "do your own time"? Using exponential random graph models and community detection methods, findings indicate that social integration is associated with better health outcomes. However, race-ethnicity, religious identity, and exercise intensity emerge as key factors sorting inmates into social groups and likely shaping the distribution of health behaviors observed in the unit.

Hierarchical communities in the walnut structure of the Japanese production network

This paper studies the structure of the Japanese production network, which includes one million firms and five million supplier-customer links. This study finds that this network forms a tightly-knit structure with a core giant strongly connected component (GSCC) surrounded by IN and OUT components constituting two half-shells of the GSCC, which we call awalnut structure because of its shape. The hierarchical structure of the communities is studied by the Infomap method, and most of the irreducible communities are found to be at the second level. The composition of some of the major communities, including overexpressions regarding their industrial or regional nature, and the connections that exist between the communities are studied in detail. The findings obtained here cause us to question the validity and accuracy of using the conventional input-output analysis, which is expected to be useful when firms in the same sectors are highly connected to each other.

Node-Based Resilience Measure Clustering with Applications to Noisy and Overlapping Communities in Complex Networks

This paper examines a schema for graph-theoretic clustering using node-based resilience measures. Node-based resilience measures optimize an objective based on a critical set of nodes whose removal causes some severity of disconnection in the network. Beyond presenting a general framework for the usage of node based resilience measures for variations of clustering problems, we experimentally validate the usefulness of such methods in accomplishing the following: (i) clustering a graph in one step without knowing the number of clusters a priori; (ii) removing noise from noisy data; and (iii) detecting overlapping communities. We demonstrate that this clustering schema can be applied successfully using a wide range of data, including both real and synthetic networks, both natively in graph form and also expressed as point sets.

Convex skeletons of complex networks

A convex network can be defined as a network such that every connected induced subgraph includes all the shortest paths between its nodes. A fully convex network would therefore be a collection of cliques stitched together in a tree. In this paper, we study the largest high-convexity part of empirical networks obtained by removing the least number of edges, which we call a convex skeleton. A convex skeleton is a generalization of a network spanning tree in which each edge can be replaced by a clique of arbitrary size. We present different approaches for extracting convex skeletons and apply them to social collaboration and protein interactions networks, autonomous systems graphs and food webs. We show that the extracted convex skeletons retain the degree distribution, clustering, connectivity, distances, node position and also community structure, while making the shortest paths between the nodes largely unique. Moreover, in the Slovenian computer scientists coauthorship network, a convex skeleton retains the strongest ties between the authors, differently from a spanning tree or high-betweenness backbone and high-salience skeleton. A convex skeleton thus represents a simple definition of a network backbone with applications in coauthorship and other social collaboration networks.

SGSG: Semantic graph-based storyline generation in Twitter

Twitter is a popular microblogging service that has become a great medium for exploring emerging events and breaking news. Unfortunately, the explosive rate of information entering Twitter makes the users experience information overload. Since a great deal of tweets revolve around news events, summarising the storyline of these events can be advantageous to users, allowing them to conveniently access relevant and key information scattered over numerous tweets and, consequently, draw concise conclusions. A storyline shows the evolution of a story through time and sketches the correlations among its significant events. In this article, we propose a novel framework for generating a storyline of news events from a social point of view. Utilising powerful concepts from graph theory, we identify the significant events, summarise them and generate a coherent storyline of their evolution with reasonable computational cost for large datasets. Our approach models a storyline as a directed tree of socially salient events evolving over time in which nodes represent main events and edges capture the semantic relations between related events. We evaluate our proposed method against human-generated storylines, as well as the previous state-of-the-art storyline generation algorithm, on two large-scale datasets, one consisting of English tweets and the other one consisting of Persian tweets. We find that the results of our method are superior to the previous best algorithm and can be comparable with human-generated storylines.

Comparative analysis on the selection of number of clusters in community detection

We conduct a comparative analysis on various estimates of the number of clusters in community detection. An exhaustive comparison requires testing of all possible combinations of frameworks, algorithms, and assessment criteria. In this paper we focus on the framework based on a stochastic block model, and investigate the performance of greedy algorithms, statistical inference, and spectral methods. For the assessment criteria, we consider modularity, map equation, Bethe free energy, prediction errors, and isolated eigenvalues. From the analysis, the tendency of overfit and underfit that the assessment criteria and algorithms have becomes apparent. In addition, we propose that the alluvial diagram is a suitable tool to visualize statistical inference results and can be useful to determine the number of clusters.

Generating global network structures by triad types

This paper addresses the question of whether one can generate networks with a given global structure (defined by selected blockmodels, i.e., cohesive, core-periphery, hierarchical, and transitivity), considering only different types of triads. Two methods are used to generate networks: (i) the newly proposed method of relocating links; and (ii) the Monte Carlo Multi Chain algorithm implemented in the ergm package in R. Most of the selected blockmodel types can be generated by considering all types of triads. The selection of only a subset of triads can improve the generated networks’ blockmodel structure. Yet, in the case of a hierarchical blockmodel without complete blocks on the diagonal, additional local structures are needed to achieve the desired global structure of generated networks. This shows that blockmodels can emerge based only on local processes that do not take attributes into account.

Constructing Temporally Extended Actions through Incremental Community Detection

Hierarchical reinforcement learning works on temporally extended actions or skills to facilitate learning. How to automatically form such abstraction is challenging, and many efforts tackle this issue in the options framework. While various approaches exist to construct options from different perspectives, few of them concentrate on options' adaptability during learning. This paper presents an algorithm to create options and enhance their quality online. Both aspects operate on detected communities of the learning environment's state transition graph. We first construct options from initial samples as the basis of online learning. Then a rule-based community revision algorithm is proposed to update graph partitions, based on which existing options can be continuously tuned. Experimental results in two problems indicate that options from initial samples may perform poorly in more complex environments, and our presented strategy can effectively improve options and get better results compared with flat reinforcement learning.