Symmetry breaking in optimal transport networks.

Engineering multilayer networks that efficiently connect sets of points in space is a crucial task in all practical applications that concern the transport of people or the delivery of goods. Unfortunately, our current theoretical understanding of the shape of such optimal transport networks is quite limited. Not much is known about how the topology of the optimal network changes as a function of its size, the relative efficiency of its layers, and the cost of switching between layers. Here, we show that optimal networks undergo sharp transitions from symmetric to asymmetric shapes, indicating that it is sometimes better to avoid serving a whole area to save on switching costs. Also, we analyze the real transportation networks of the cities of Atlanta, Boston, and Toronto using our theoretical framework and find that they are farther away from their optimal shapes as traffic congestion increases.

Collaboration and topic switches in science.

Collaboration is a key driver of science and innovation. Mainly motivated by the need to leverage different capacities and expertise to solve a scientific problem, collaboration is also an excellent source of information about the future behavior of scholars. In particular, it allows us to infer the likelihood that scientists choose future research directions via the intertwined mechanisms of selection and social influence. Here we thoroughly investigate the interplay between collaboration and topic switches. We find that the probability for a scholar to start working on a new topic increases with the number of previous collaborators, with a pattern showing that the effects of individual collaborators are not independent. The higher the productivity and the impact of authors, the more likely their coworkers will start working on new topics. The average number of coauthors per paper is also inversely related to the topic switch probability, suggesting a dilution of this effect as the number of collaborators increases.

Influence maximization: Divide and conquer.

The problem of influence maximization, i.e., finding the set of nodes having maximal influence on a network, is of great importance for several applications. In the past two decades, many heuristic metrics to spot influencers have been proposed. Here, we introduce a framework to boost the performance of such metrics. The framework consists in dividing the network into sectors of influence, and then selecting the most influential nodes within these sectors. We explore three different methodologies to find sectors in a network: graph partitioning, graph hyperbolic embedding, and community structure. The framework is validated with a systematic analysis of real and synthetic networks. We show that the gain in performance generated by dividing a network into sectors before selecting the influential spreaders increases as the modularity and heterogeneity of the network increase. Also, we show that the division of the network into sectors can be efficiently performed in a time that scales linearly with the network size, thus making the framework applicable to large-scale influence maximization problems.

Robustness modularity in complex networks.

A basic question in network community detection is how modular a given network is. This is usually addressed by evaluating the quality of partitions detected in the network. The Girvan-Newman (GN) modularity function is the standard way to make this assessment, but it has a number of drawbacks. Most importantly, it is not clearly interpretable, given that the measure can take relatively large values on partitions of random networks without communities. Here we propose a measure based on the concept of robustness: modularity is the probability to find trivial partitions when the structure of the network is randomly perturbed. This concept can be implemented for any clustering algorithm capable of telling when a group structure is absent. Tests on artificial and real graphs reveal that robustness modularity can be used to assess and compare the strength of the community structure of different networks. We also introduce two other quality functions: modularity difference, a suitably normalized version of the GN modularity, and information modularity, a measure of distance based on information compression. Both measures are strongly correlated with robustness modularity, but have lower time complexity, so they could be used on networks whose size makes the calculation of robustness modularity too costly.

Community detection in networks using graph embeddings.

Graph embedding methods are becoming increasingly popular in the machine learning community, where they are widely used for tasks such as node classification and link prediction. Embedding graphs in geometric spaces should aid the identification of network communities as well because nodes in the same community should be projected close to each other in the geometric space, where they can be detected via standard data clustering algorithms. In this paper, we test the ability of several graph embedding techniques to detect communities on benchmark graphs. We compare their performance against that of traditional community detection algorithms. We find that the performance is comparable, if the parameters of the embedding techniques are suitably chosen. However, the optimal parameter set varies with the specific features of the benchmark graphs, like their size, whereas popular community detection algorithms do not require any parameter. So, it is not possible to indicate beforehand good parameter sets for the analysis of real networks. This finding, along with the high computational cost of embedding a network and grouping the points, suggests that, for community detection, current embedding techniques do not represent an improvement over network clustering algorithms.

Multiscale community detection in Cytoscape.

Detection of community structure has become a fundamental step in the analysis of biological networks with application to protein function annotation, disease gene prediction, and drug discovery. This recent impact creates a need to make these techniques and their accompanying visualization schemes available to a broad range of biologists. Here we present a service-oriented, end-to-end software framework, CDAPS (Community Detection APplication and Service), that integrates the identification, annotation, visualization, and interrogation of multiscale network communities, accessible within the popular Cytoscape network analysis platform. With novel design principles, CDAPS addresses unmet new challenges, such as identifying hierarchical community structures, comparison of outputs generated from diverse network resources, and easy deployment of new algorithms, to facilitate community-sourced science. We demonstrate that the CDAPS framework can be applied to high-throughput protein-protein interaction networks to gain novel insights, such as the identification of putative new members of known protein complexes.

Scientific elite revisited: patterns of productivity, collaboration, authorship and impact.

Throughout history, a relatively small number of individuals have made a profound and lasting impact on science and society. Despite long-standing, multi-disciplinary interests in understanding careers of elite scientists, there have been limited attempts for a quantitative, career-level analysis. Here, we leverage a comprehensive dataset we assembled, allowing us to trace the entire career histories of nearly all Nobel laureates in physics, chemistry, and physiology or medicine over the past century. We find that, although Nobel laureates were energetic producers from the outset, producing works that garner unusually high impact, their careers before winning the prize follow relatively similar patterns to those of ordinary scientists, being characterized by hot streaks and increasing reliance on collaborations. We also uncovered notable variations along their careers, often associated with the Nobel Prize, including shifting coauthorship structure in the prize-winning work, and a significant but temporary dip in the impact of work they produce after winning the Nobel Prize. Together, these results document quantitative patterns governing the careers of scientific elites, offering an empirical basis for a deeper understanding of the hallmarks of exceptional careers in science.

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.

A dataset of publication records for Nobel laureates.

A central question in the science of science concerns how to develop a quantitative understanding of the evolution and impact of individual careers. Over the course of history, a relatively small fraction of individuals have made disproportionate, profound, and lasting impacts on science and society. Despite a long-standing interest in the careers of scientific elites across diverse disciplines, it remains difficult to collect large-scale career histories that could serve as training sets for systematic empirical and theoretical studies. Here, by combining unstructured data collected from CVs, university websites, and Wikipedia, together with the publication and citation database from Microsoft Academic Graph (MAG), we reconstructed publication histories of nearly all Nobel prize winners from the past century, through both manual curation and algorithmic disambiguation procedures. Data validation shows that the collected dataset presents among the most comprehensive collection of publication records for Nobel laureates currently available. As our quantitative understanding of science deepens, this dataset is expected to have increasing value. It will not only allow us to quantitatively probe novel patterns of productivity, collaboration, and impact governing successful scientific careers, it may also help us unearth the fundamental principles underlying creativity and the genesis of scientific breakthroughs.

Resting state network modularity along the prodromal late onset Alzheimer's disease continuum.

Alzheimer's disease is considered a disconnection syndrome, motivating the use of brain network measures to detect changes in whole-brain resting state functional connectivity (FC). We investigated changes in FC within and among resting state networks (RSN) across four different stages in the Alzheimer's disease continuum. FC changes were examined in two independent cohorts of individuals (84 and 58 individuals, respectively) each comprising control, subjective cognitive decline, mild cognitive impairment and Alzheimer's dementia groups. For each participant, FC was computed as a matrix of Pearson correlations between pairs of time series from 278 gray matter brain regions. We determined significant differences in FC modular organization with two distinct approaches, network contingency analysis and multiresolution consensus clustering. Network contingency analysis identified RSN sub-blocks that differed significantly across clinical groups. Multiresolution consensus clustering identified differences in the stability of modules across multiple spatial scales. Significant modules were further tested for statistical association with memory and executive function cognitive domain scores. Across both analytic approaches and in both participant cohorts, the findings converged on a pattern of FC that varied systematically with diagnosis within the frontoparietal network (FP) and between the FP network and default mode network (DMN). Disturbances of modular organization were manifest as greater internal coherence of the FP network and stronger coupling between FP and DMN, resulting in less segregation of these two networks. Our findings suggest that the pattern of interactions within and between specific RSNs offers new insight into the functional disruption that occurs across the Alzheimer's disease spectrum.

Subsystem organization of axonal connections within and between the right and left cerebral cortex and cerebral nuclei (endbrain).

The endbrain (telencephalon) is at the rostral end of the central nervous system and is primarily responsible for supporting cognition and affect. Structurally, it consists of right and left cerebral hemispheres, each parceled into multiple cortical and nuclear gray matter regions. The global network organization of axonal macroconnections between the 244 regions forming the endbrain was analyzed with a multiresolution consensus clustering (MRCC) method that provides a hierarchical description of community clustering (modules or subsystems) within the network. Experimental evidence was collated from the neuroanatomical literature for the existence of 10,002 of a possible 59,292 connections within the network, and they cluster into four top-level subsystems and 60 bottom-level subsystems arranged in a 50-level hierarchy. Two top-level subsystems are bihemispheric: One deals with auditory and visual information, and the other corresponds broadly to the default mode network. The other two top-level subsystems are bilaterally symmetrical, and each deals broadly with somatic and visceral information. Because the entire endbrain connection matrix was assembled from multiple subconnectomes, it was easy to show that the status of a region as a connectivity hub is not absolute but, instead, depends on the size and coverage of its anatomical neighborhood. It was also shown numerically that creating an ultradense connection matrix by converting all "absent" connections to a "very weak" connection weight has virtually no effect on the clustering hierarchy. The next logical step in this project is to complete the forebrain connectome by adding the thalamus and hypothalamus (together, the interbrain) to the endbrain analysis.

Science of science.

Identifying fundamental drivers of science and developing predictive models to capture its evolution are instrumental for the design of policies that can improve the scientific enterprise-for example, through enhanced career paths for scientists, better performance evaluation for organizations hosting research, discovery of novel effective funding vehicles, and even identification of promising regions along the scientific frontier. The science of science uses large-scale data on the production of science to search for universal and domain-specific patterns. Here, we review recent developments in this transdisciplinary field.

Multiresolution Consensus Clustering in Networks.

Networks often exhibit structure at disparate scales. We propose a method for identifying community structure at different scales based on multiresolution modularity and consensus clustering. Our contribution consists of two parts. First, we propose a strategy for sampling the entire range of possible resolutions for the multiresolution modularity quality function. Our approach is directly based on the properties of modularity and, in particular, provides a natural way of avoiding the need to increase the resolution parameter by several orders of magnitude to break a few remaining small communities, necessitating the introduction of ad-hoc limits to the resolution range with standard sampling approaches. Second, we propose a hierarchical consensus clustering procedure, based on a modified modularity, that allows one to construct a hierarchical consensus structure given a set of input partitions. While here we are interested in its application to partitions sampled using multiresolution modularity, this consensus clustering procedure can be applied to the output of any clustering algorithm. As such, we see many potential applications of the individual parts of our multiresolution consensus clustering procedure in addition to using the procedure itself to identify hierarchical structure in networks.

Reconfiguration of Cortical Networks in MDD Uncovered by Multiscale Community Detection with fMRI.

Major depressive disorder (MDD) is known to be associated with altered interactions between distributed brain regions. How these regional changes relate to the reorganization of cortical functional systems, and their modulation by antidepressant medication, is relatively unexplored. To identify changes in the community structure of cortical functional networks in MDD, we performed a multiscale community detection algorithm on resting-state functional connectivity networks of unmedicated MDD (uMDD) patients (n = 46), medicated MDD (mMDD) patients (n = 38), and healthy controls (n = 50), which yielded a spectrum of multiscale community partitions. we selected an optimal resolution level by identifying the most stable community partition for each group. uMDD and mMDD groups exhibited a similar reconfiguration of the community structure of the visual association and the default mode systems but showed different reconfiguration profiles in the frontoparietal control (FPC) subsystems. Furthermore, the central system (somatomotor/salience) and 3 frontoparietal subsystems showed strengthened connectivity with other communities in uMDD but, with the exception of 1 frontoparietal subsystem, returned to control levels in mMDD. These findings provide evidence for reconfiguration of specific cortical functional systems associated with MDD, as well as potential effects of medication in restoring disease-related network alterations, especially those of the FPC system.

Detection of timescales in evolving complex systems.

Most complex systems are intrinsically dynamic in nature. The evolution of a dynamic complex system is typically represented as a sequence of snapshots, where each snapshot describes the configuration of the system at a particular instant of time. This is often done by using constant intervals but a better approach would be to define dynamic intervals that match the evolution of the system's configuration. To this end, we propose a method that aims at detecting evolutionary changes in the configuration of a complex system, and generates intervals accordingly. We show that evolutionary timescales can be identified by looking for peaks in the similarity between the sets of events on consecutive time intervals of data. Tests on simple toy models reveal that the technique is able to detect evolutionary timescales of time-varying data both when the evolution is smooth as well as when it changes sharply. This is further corroborated by analyses of several real datasets. Our method is scalable to extremely large datasets and is computationally efficient. This allows a quick, parameter-free detection of multiple timescales in the evolution of a complex system.

Publisher's Note: Eigenvector dynamics under perturbation of modular networks [Phys. Rev. E 93, 062312 (2016)].

This corrects the article DOI: 10.1103/PhysRevE.93.062312.

Eigenvector dynamics under perturbation of modular networks.

Rotation dynamics of eigenvectors of modular network adjacency matrices under random perturbations are presented. In the presence of q communities, the number of eigenvectors corresponding to the q largest eigenvalues form a "community" eigenspace and rotate together, but separately from that of the "bulk" eigenspace spanned by all the other eigenvectors. Using this property, the number of modules or clusters in a network can be estimated in an algorithm-independent way. A general argument and derivation for the theoretical detectability limit for sparse modular networks with q communities is presented, beyond which modularity persists in the system but cannot be detected. It is shown that for detecting the clusters or modules using the adjacency matrix, there is a "band" in which it is hard to detect the clusters even before the theoretical detectability limit is reached, and for which the theoretically predicted detectability limit forms the sufficient upper bound. Analytic estimations of these bounds are presented and empirically demonstrated.

Detection of gene communities in multi-networks reveals cancer drivers.

We propose a new multi-network-based strategy to integrate different layers of genomic information and use them in a coordinate way to identify driving cancer genes. The multi-networks that we consider combine transcription factor co-targeting, microRNA co-targeting, protein-protein interaction and gene co-expression networks. The rationale behind this choice is that gene co-expression and protein-protein interactions require a tight coregulation of the partners and that such a fine tuned regulation can be obtained only combining both the transcriptional and post-transcriptional layers of regulation. To extract the relevant biological information from the multi-network we studied its partition into communities. To this end we applied a consensus clustering algorithm based on state of art community detection methods. Even if our procedure is valid in principle for any pathology in this work we concentrate on gastric, lung, pancreas and colorectal cancer and identified from the enrichment analysis of the multi-network communities a set of candidate driver cancer genes. Some of them were already known oncogenes while a few are new. The combination of the different layers of information allowed us to extract from the multi-network indications on the regulatory pattern and functional role of both the already known and the new candidate driver genes.

Quantifying randomness in real networks.

Represented as graphs, real networks are intricate combinations of order and disorder. Fixing some of the structural properties of network models to their values observed in real networks, many other properties appear as statistical consequences of these fixed observables, plus randomness in other respects. Here we employ the dk-series, a complete set of basic characteristics of the network structure, to study the statistical dependencies between different network properties. We consider six real networks--the Internet, US airport network, human protein interactions, technosocial web of trust, English word network, and an fMRI map of the human brain--and find that many important local and global structural properties of these networks are closely reproduced by dk-random graphs whose degree distributions, degree correlations and clustering are as in the corresponding real network. We discuss important conceptual, methodological, and practical implications of this evaluation of network randomness, and release software to generate dk-random graphs.

Benchmark model to assess community structure in evolving networks.

Detecting the time evolution of the community structure of networks is crucial to identify major changes in the internal organization of many complex systems, which may undergo important endogenous or exogenous events. This analysis can be done in two ways: considering each snapshot as an independent community detection problem or taking into account the whole evolution of the network. In the first case, one can apply static methods on the temporal snapshots, which correspond to configurations of the system in short time windows, and match afterward the communities across layers. Alternatively, one can develop dedicated dynamic procedures so that multiple snapshots are simultaneously taken into account while detecting communities, which allows us to keep memory of the flow. To check how well a method of any kind could capture the evolution of communities, suitable benchmarks are needed. Here we propose a model for generating simple dynamic benchmark graphs, based on stochastic block models. In them, the time evolution consists of a periodic oscillation of the system's structure between configurations with built-in community structure. We also propose the extension of quality comparison indices to the dynamic scenario.