Community detection algorithms: a comparative analysis

Mesoscopic analysis of online social networks: the role of negative ties

A class of networks are those with both positive and negative links. In this manuscript, we studied the interplay between positive and negative ties on mesoscopic level of these networks, i.e., their community structure. A community is considered as a tightly interconnected group of actors; therefore, it does not borrow any assumption from balance theory and merely uses the well-known assumption in the community detection literature. We found that if one detects the communities based on only positive relations (by ignoring the negative ones), the majority of negative relations are already placed between the communities. In other words, negative ties do not have a major role in community formation of signed networks. Moreover, regarding the internal negative ties, we proved that most unbalanced communities are maximally balanced, and hence they cannot be partitioned into k nonempty sub-clusters with higher balancedness (k≥2). Furthermore, we showed that although the mediator triad ++- (hostile-mediator-hostile) is underrepresented, it constitutes a considerable portion of triadic relations among communities. Hence, mediator triads should not be ignored by community detection and clustering algorithms. As a result, if one uses a clustering algorithm that operates merely based on social balance, mesoscopic structure of signed networks significantly remains hidden.

Uncovering community structures with initialized Bayesian nonnegative matrix factorization

Uncovering community structures is important for understanding networks. Currently, several nonnegative matrix factorization algorithms have been proposed for discovering community structure in complex networks. However, these algorithms exhibit some drawbacks, such as unstable results and inefficient running times. In view of the problems, a novel approach that utilizes an initialized Bayesian nonnegative matrix factorization model for determining community membership is proposed. First, based on singular value decomposition, we obtain simple initialized matrix factorizations from approximate decompositions of the complex network’s adjacency matrix. Then, within a few iterations, the final matrix factorizations are achieved by the Bayesian nonnegative matrix factorization method with the initialized matrix factorizations. Thus, the network’s community structure can be determined by judging the classification of nodes with a final matrix factor. Experimental results show that the proposed method is highly accurate and offers competitive performance to that of the state-of-the-art methods even though it is not designed for the purpose of modularity maximization.

Generic criticality of community structure in random graphs

We examine a community structure in random graphs of size n and link probability p/n determined with the Newman greedy optimization of modularity. Calculations show that for p<1 communities are nearly identical with clusters. For p=1 the average sizes of a community s(av) and of the giant community s(g) show a power-law increase s(av)∼n(α') and s(g)∼n(α). From numerical results we estimate α'≈0.26(1) and α≈0.50(1) and using the probability distribution of sizes of communities we suggest that α'=α/2 should hold. For p>1 the community structure remains critical: (i) s(av) and s(g) have a power-law increase with α'≈α<1 and (ii) the probability distribution of sizes of communities is very broad and nearly flat for all sizes up to s(g). For large p the modularity Q decays as Q∼p(-0.55), which is intermediate between some previous estimations. To check the validity of the results, we also determine the community structure using another method, namely, a nongreedy optimization of modularity. Tests with some benchmark networks show that the method outperforms the greedy version. For random graphs, however, the characteristics of the community structure determined using both greedy and nongreedy optimizations are, within small statistical fluctuations, the same.

Bootstrapping on undirected binary networks via statistical mechanics

We propose a new method inspired from statistical mechanics for extracting geometric information from undirected binary networks and generating random networks that conform to this geometry. In this method an undirected binary network is perceived as a thermodynamic system with a collection of permuted adjacency matrices as its states. The task of extracting information from the network is then reformulated as a discrete combinatorial optimization problem of searching for its ground state. To solve this problem, we apply multiple ensembles of temperature regulated Markov chains to establish an ultrametric geometry on the network. This geometry is equipped with a tree hierarchy that captures the multiscale community structure of the network. We translate this geometry into a Parisi adjacency matrix, which has a relative low energy level and is in the vicinity of the ground state. The Parisi adjacency matrix is then further optimized by making block permutations subject to the ultrametric geometry. The optimal matrix corresponds to the macrostate of the original network. An ensemble of random networks is then generated such that each of these networks conforms to this macrostate; the corresponding algorithm also provides an estimate of the size of this ensemble. By repeating this procedure at different scales of the ultrametric geometry of the network, it is possible to compute its evolution entropy, i.e. to estimate the evolution of its complexity as we move from a coarse to a ne description of its geometric structure. We demonstrate the performance of this method on simulated as well as real data networks.

Robust brain parcellation using sparse representation on resting-state fMRI

Resting-state fMRI (rs-fMRI) has been widely used to segregate the brain into individual modules based on the presence of distinct connectivity patterns. Many parcellation methods have been proposed for brain parcellation using rs-fMRI, but their results have been somewhat inconsistent, potentially due to various types of noise. In this study, we provide a robust parcellation method for rs-fMRI-based brain parcellation, which constructs a sparse similarity graph based on the sparse representation coefficients of each seed voxel and then uses spectral clustering to identify distinct modules. Both the local time-varying BOLD signals and whole-brain connectivity patterns may be used as features and yield similar parcellation results. The robustness of our method was tested on both simulated and real rs-fMRI datasets. In particular, on simulated rs-fMRI data, sparse representation achieved good performance across different noise levels, including high accuracy of parcellation and high robustness to noise. On real rs-fMRI data, stable parcellation of the medial frontal cortex (MFC) and parietal operculum (OP) were achieved on three different datasets, with high reproducibility within each dataset and high consistency across these results. Besides, the parcellation of MFC was little influenced by the degrees of spatial smoothing. Furthermore, the consistent parcellation of OP was also well corresponding to cytoarchitectonic subdivisions and known somatotopic organizations. Our results demonstrate a new promising approach to robust brain parcellation using resting-state fMRI by sparse representation.

The community structure of the global corporate network

We investigate the community structure of the global ownership network of transnational corporations. We find a pronounced organization in communities that cannot be explained by randomness. Despite the global character of this network, communities reflect first of all the geographical location of firms, while the industrial sector plays only a marginal role. We also analyze the meta-network in which the nodes are the communities and the links are obtained by aggregating the links among firms belonging to pairs of communities. We analyze the network centrality of the top 50 communities and we provide a quantitative assessment of the financial sector role in connecting the global economy.

Stock portfolio structure of individual investors infers future trading behavior

Although the understanding of and motivation behind individual trading behavior is an important puzzle in finance, little is known about the connection between an investor's portfolio structure and her trading behavior in practice. In this paper, we investigate the relation between what stocks investors hold, and what stocks they buy, and show that investors with similar portfolio structures to a great extent trade in a similar way. With data from the central register of shareholdings in Sweden, we model the market in a similarity network, by considering investors as nodes, connected with links representing portfolio similarity. From the network, we find investor groups that not only identify different investment strategies, but also represent individual investors trading in a similar way. These findings suggest that the stock portfolios of investors hold meaningful information, which could be used to earn a better understanding of stock market dynamics.

Online community detection for large complex networks

Complex networks describe a wide range of systems in nature and society. To understand complex networks, it is crucial to investigate their community structure. In this paper, we develop an online community detection algorithm with linear time complexity for large complex networks. Our algorithm processes a network edge by edge in the order that the network is fed to the algorithm. If a new edge is added, it just updates the existing community structure in constant time, and does not need to re-compute the whole network. Therefore, it can efficiently process large networks in real time. Our algorithm optimizes expected modularity instead of modularity at each step to avoid poor performance. The experiments are carried out using 11 public data sets, and are measured by two criteria, modularity and NMI (Normalized Mutual Information). The results show that our algorithm's running time is less than the commonly used Louvain algorithm while it gives competitive performance.

Detecting communities based on network topology

Network methods have had profound influence in many domains and disciplines in the past decade. Community structure is a very important property of complex networks, but the accurate definition of a community remains an open problem. Here we defined community based on three properties, and then propose a simple and novel framework to detect communities based on network topology. We analyzed 16 different types of networks, and compared our partitions with Infomap, LPA, Fastgreedy and Walktrap, which are popular algorithms for community detection. Most of the partitions generated using our approach compare favorably to those generated by these other algorithms. Furthermore, we define overlapping nodes that combine community structure with shortest paths. We also analyzed the E. Coli. transcriptional regulatory network in detail, and identified modules with strong functional coherence.

The role of endogenous and exogenous mechanisms in the formation of R&D networks

We develop an agent-based model of strategic link formation in Research and Development (R&D) networks. Empirical evidence has shown that the growth of these networks is driven by mechanisms which are both endogenous to the system (that is, depending on existing alliances patterns) and exogenous (that is, driven by an exploratory search for newcomer firms). Extant research to date has not investigated both mechanisms simultaneously in a comparative manner. To overcome this limitation, we develop a general modeling framework to shed light on the relative importance of these two mechanisms. We test our model against a comprehensive dataset, listing cross-country and cross-sectoral R&D alliances from 1984 to 2009. Our results show that by fitting only three macroscopic properties of the network topology, this framework is able to reproduce a number of micro-level measures, including the distributions of degree, local clustering, path length and component size, and the emergence of network clusters. Furthermore, by estimating the link probabilities towards newcomers and established firms from the data, we find that endogenous mechanisms are predominant over the exogenous ones in the network formation, thus quantifying the importance of existing structures in selecting partner firms.

General optimization technique for high-quality community detection in complex networks

Recent years have witnessed the development of a large body of algorithms for community detection in complex networks. Most of them are based upon the optimization of objective functions, among which modularity is the most common, though a number of alternatives have been suggested in the scientific literature. We present here an effective general search strategy for the optimization of various objective functions for community detection purposes. When applied to modularity, on both real-world and synthetic networks, our search strategy substantially outperforms the best existing algorithms in terms of final scores of the objective function. In terms of execution time for modularity optimization this approach also outperforms most of the alternatives present in literature with the exception of fastest but usually less efficient greedy algorithms. The networks of up to 30000 nodes can be analyzed in time spans ranging from minutes to a few hours on average workstations, making our approach readily applicable to tasks not limited by strict time constraints but requiring the quality of partitioning to be as high as possible. Some examples are presented in order to demonstrate how this quality could be affected by even relatively small changes in the modularity score stressing the importance of optimization accuracy.

Detecting network communities beyond assortativity-related attributes

In network science, assortativity refers to the tendency of links to exist between nodes with similar attributes. In social networks, for example, links tend to exist between individuals of similar age, nationality, location, race, income, educational level, religious belief, and language. Thus, various attributes jointly affect the network topology. An interesting problem is to detect community structure beyond some specific assortativity-related attributes ρ, i.e., to take out the effect of ρ on network topology and reveal the hidden community structures which are due to other attributes. An approach to this problem is to redefine the null model of the modularity measure, so as to simulate the effect of ρ on network topology. However, a challenge is that we do not know to what extent the network topology is affected by ρ and by other attributes. In this paper, we propose a distance modularity, which allows us to freely choose any suitable function to simulate the effect of ρ. Such freedom can help us probe the effect of ρ and detect the hidden communities which are due to other attributes. We test the effectiveness of distance modularity on synthetic benchmarks and two real-world networks.

Exploring function prediction in protein interaction networks via clustering methods

Complex networks have recently become the focus of research in many fields. Their structure reveals crucial information for the nodes, how they connect and share information. In our work we analyze protein interaction networks as complex networks for their functional modular structure and later use that information in the functional annotation of proteins within the network. We propose several graph representations for the protein interaction network, each having different level of complexity and inclusion of the annotation information within the graph. We aim to explore what the benefits and the drawbacks of these proposed graphs are, when they are used in the function prediction process via clustering methods. For making this cluster based prediction, we adopt well established approaches for cluster detection in complex networks using most recent representative algorithms that have been proven as efficient in the task at hand. The experiments are performed using a purified and reliable Saccharomyces cerevisiae protein interaction network, which is then used to generate the different graph representations. Each of the graph representations is later analysed in combination with each of the clustering algorithms, which have been possibly modified and implemented to fit the specific graph. We evaluate results in regards of biological validity and function prediction performance. Our results indicate that the novel ways of presenting the complex graph improve the prediction process, although the computational complexity should be taken into account when deciding on a particular approach.

Exploring community structure in biological networks with random graphs

Background

Community structure is ubiquitous in biological networks. There has been an increased interest in unraveling the community structure of biological systems as it may provide important insights into a system’s functional components and the impact of local structures on dynamics at a global scale. Choosing an appropriate community detection algorithm to identify the community structure in an empirical network can be difficult, however, as the many algorithms available are based on a variety of cost functions and are difficult to validate. Even when community structure is identified in an empirical system, disentangling the effect of community structure from other network properties such as clustering coefficient and assortativity can be a challenge.

Results

Here, we develop a generative model to produce undirected, simple, connected graphs with a specified degrees and pattern of communities, while maintaining a graph structure that is as random as possible. Additionally, we demonstrate two important applications of our model: (a) to generate networks that can be used to benchmark existing and new algorithms for detecting communities in biological networks; and (b) to generate null models to serve as random controls when investigating the impact of complex network features beyond the byproduct of degree and modularity in empirical biological networks.

Conclusion

Our model allows for the systematic study of the presence of community structure and its impact on network function and dynamics. This process is a crucial step in unraveling the functional consequences of the structural properties of biological systems and uncovering the mechanisms that drive these systems.

Controllability and observability analysis for vertex domination centrality in directed networks

Topological centrality is a significant measure for characterising the relative importance of a node in a complex network. For directed networks that model dynamic processes, however, it is of more practical importance to quantify a vertex's ability to dominate (control or observe) the state of other vertices. In this paper, based on the determination of controllable and observable subspaces under the global minimum-cost condition, we introduce a novel direction-specific index, domination centrality, to assess the intervention capabilities of vertices in a directed network. Statistical studies demonstrate that the domination centrality is, to a great extent, encoded by the underlying network's degree distribution and that most network positions through which one can intervene in a system are vertices with high domination centrality rather than network hubs. To analyse the interaction and functional dependence between vertices when they are used to dominate a network, we define the domination similarity and detect significant functional modules in glossary and metabolic networks through clustering analysis. The experimental results provide strong evidence that our indices are effective and practical in accurately depicting the structure of directed networks.

Constant communities in complex networks

Identifying community structure is a fundamental problem in network analysis. Most community detection algorithms are based on optimizing a combinatorial parameter, for example modularity. This optimization is generally NP-hard, thus merely changing the vertex order can alter their assignments to the community. However, there has been less study on how vertex ordering influences the results of the community detection algorithms. Here we identify and study the properties of invariant groups of vertices (constant communities) whose assignment to communities are, quite remarkably, not affected by vertex ordering. The percentage of constant communities can vary across different applications and based on empirical results we propose metrics to evaluate these communities. Using constant communities as a pre-processing step, one can significantly reduce the variation of the results. Finally, we present a case study on phoneme network and illustrate that constant communities, quite strikingly, form the core functional units of the larger communities.

Multilevel hierarchical kernel spectral clustering for real-life large scale complex networks

Kernel spectral clustering corresponds to a weighted kernel principal component analysis problem in a constrained optimization framework. The primal formulation leads to an eigen-decomposition of a centered Laplacian matrix at the dual level. The dual formulation allows to build a model on a representative subgraph of the large scale network in the training phase and the model parameters are estimated in the validation stage. The KSC model has a powerful out-of-sample extension property which allows cluster affiliation for the unseen nodes of the big data network. In this paper we exploit the structure of the projections in the eigenspace during the validation stage to automatically determine a set of increasing distance thresholds. We use these distance thresholds in the test phase to obtain multiple levels of hierarchy for the large scale network. The hierarchical structure in the network is determined in a bottom-up fashion. We empirically showcase that real-world networks have multilevel hierarchical organization which cannot be detected efficiently by several state-of-the-art large scale hierarchical community detection techniques like the Louvain, OSLOM and Infomap methods. We show that a major advantage of our proposed approach is the ability to locate good quality clusters at both the finer and coarser levels of hierarchy using internal cluster quality metrics on 7 real-life networks.

Dynamic social community detection and its applications

Community structure is one of the most commonly observed features of Online Social Networks (OSNs) in reality. The knowledge of this feature is of great advantage: it not only provides helpful insights into developing more efficient social-aware solutions but also promises a wide range of applications enabled by social and mobile networking, such as routing strategies in Mobile Ad Hoc Networks (MANETs) and worm containment in OSNs. Unfortunately, understanding this structure is very challenging, especially in dynamic social networks where social interactions are evolving rapidly. Our work focuses on the following questions: How can we efficiently identify communities in dynamic social networks? How can we adaptively update the network community structure based on its history instead of recomputing from scratch? To this end, we present Quick Community Adaptation (QCA), an adaptive modularity-based framework for not only discovering but also tracing the evolution of network communities in dynamic OSNs. QCA is very fast and efficient in the sense that it adaptively updates and discovers the new community structure based on its history together with the network changes only. This flexible approach makes QCA an ideal framework applicable for analyzing large-scale dynamic social networks due to its lightweight computing-resource requirement. To illustrate the effectiveness of our framework, we extensively test QCA on both synthesized and real-world social networks including Enron, arXiv e-print citation, and Facebook networks. Finally, we demonstrate the applicability of QCA in real applications: (1) A social-aware message forwarding strategy in MANETs, and (2) worm propagation containment in OSNs. Competitive results in comparison with other methods reveal that social-based techniques employing QCA as a community detection core outperform current available methods.

Game theory and extremal optimization for community detection in complex dynamic networks

The detection of evolving communities in dynamic complex networks is a challenging problem that recently received attention from the research community. Dynamics clearly add another complexity dimension to the difficult task of community detection. Methods should be able to detect changes in the network structure and produce a set of community structures corresponding to different timestamps and reflecting the evolution in time of network data. We propose a novel approach based on game theory elements and extremal optimization to address dynamic communities detection. Thus, the problem is formulated as a mathematical game in which nodes take the role of players that seek to choose a community that maximizes their profit viewed as a fitness function. Numerical results obtained for both synthetic and real-world networks illustrate the competitive performance of this game theoretical approach.

A comparative analysis of computational approaches and algorithms for protein subcomplex identification

High-throughput AP-MS methods have allowed the identification of many protein complexes. However, most post-processing methods of this type of data have been focused on detection of protein complexes and not its subcomplexes. Here, we review the results of some existing methods that may allow subcomplex detection and propose alternative methods in order to detect subcomplexes from AP-MS data. We assessed and drew comparisons between the use of overlapping clustering methods, methods based in the core-attachment model and our own prediction strategy (TRIBAL). The hypothesis behind TRIBAL is that subcomplex-building information may be concealed in the multiple edges generated by an interaction repeated in different contexts in raw data. The CACHET method offered the best results when the evaluation of the predicted subcomplexes was carried out using both the hypergeometric and geometric scores. TRIBAL offered the best performance when using a strict meet-min score.

Improving the performance of algorithms to find communities in networks

Most algorithms to detect communities in networks typically work without any information on the cluster structure to be found, as one has no a priori knowledge of it, in general. Not surprisingly, knowing some features of the unknown partition could help its identification, yielding an improvement of the performance of the method. Here we show that, if the number of clusters was known beforehand, standard methods, like modularity optimization, would considerably gain in accuracy, mitigating the severe resolution bias that undermines the reliability of the results of the original unconstrained version. The number of clusters can be inferred from the spectra of the recently introduced nonbacktracking and flow matrices, even in benchmark graphs with realistic community structure. The limit of such a two-step procedure is the overhead of the computation of the spectra.

Exploring the limits of community detection strategies in complex networks

The characterization of network community structure has profound implications in several scientific areas. Therefore, testing the algorithms developed to establish the optimal division of a network into communities is a fundamental problem in the field. We performed here a highly detailed evaluation of community detection algorithms, which has two main novelties: 1) using complex closed benchmarks, which provide precise ways to assess whether the solutions generated by the algorithms are optimal; and, 2) A novel type of analysis, based on hierarchically clustering the solutions suggested by multiple community detection algorithms, which allows to easily visualize how different are those solutions. Surprise, a global parameter that evaluates the quality of a partition, confirms the power of these analyses. We show that none of the community detection algorithms tested provide consistently optimal results in all networks and that Surprise maximization, obtained by combining multiple algorithms, obtains quasi-optimal performances in these difficult benchmarks.

The multiscale backbone of the human phenotype network based on biological pathways

Background

Networks are commonly used to represent and analyze large and complex systems of interacting elements. In systems biology, human disease networks show interactions between disorders sharing common genetic background. We built pathway-based human phenotype network (PHPN) of over 800 physical attributes, diseases, and behavioral traits; based on about 2,300 genes and 1,200 biological pathways. Using GWAS phenotype-to-genes associations, and pathway data from Reactome, we connect human traits based on the common patterns of human biological pathways, detecting more pleiotropic effects, and expanding previous studies from a gene-centric approach to that of shared cell-processes.

Results

The resulting network has a heavily right-skewed degree distribution, placing it in the scale-free region of the network topologies spectrum. We extract the multi-scale information backbone of the PHPN based on the local densities of the network and discarding weak connection. Using a standard community detection algorithm, we construct phenotype modules of similar traits without applying expert biological knowledge. These modules can be assimilated to the disease classes. However, we are able to classify phenotypes according to shared biology, and not arbitrary disease classes. We present examples of expected clinical connections identified by PHPN as proof of principle.

Conclusions

We unveil a previously uncharacterized connection between phenotype modules and discuss potential mechanistic connections that are obvious only in retrospect. The PHPN shows tremendous potential to become a useful tool both in the unveiling of the diseases’ common biology, and in the elaboration of diagnosis and treatments.

Network medicine analysis of chondrocyte proteins towards new treatments of osteoarthritis

Osteoarthritis (OA) is a progressive disorder with high incidence in the ageing human population that still has no treatment currently. This disorder induces the breakdown of articular cartilage, leading to the exposure and damage of bone surfaces. For a global understanding of OA development, the systematic integration of known OA-related proteins with protein-protein interaction (PPI) networks is required. In this work, the OA-related interactome was reconstructed using multiple data sources to have the most up-to-date information on OA-related proteins and their interactions. We then combined emergent concepts in network medicine to detect new unclassified OA-related proteins. The mapping of known OA-related proteins with PPI networks showed that these proteins are locally connected to each other and agglomerated in a large component. To expand this module, we applied a diffusion-based algorithm that probabilistically induces more searches in the vicinity of the seed OA-related proteins. As a result, the 10 topmost ranked proteins were connected to the OA disease module, supporting the local hypothesis. We computed structural modules and selected those that had the highest enrichment of OA-related proteins. The identified molecules show a link between structural topology and disease dysfunctionality. Interestingly, the protein Q6EEV6 was highlighted for OA association by both methods, reinforcing the potential involvement of this protein. These results suggest that similar disease-connected modules may exist in different human disorders, which could lead to systematic identification of genes or proteins that have a joint role in specific disease phenotypes.

Community analysis in directed networks: in-, out-, and pseudocommunities

When analyzing important classes of complex interconnected systems, link directionality can hardly be neglected if a precise and effective picture of the structure and function of the system is needed. If community analysis is performed, the notion of "community" itself is called into question, since the property of having a comparatively looser external connectivity could refer to the inbound or outbound links only or to both categories. In this paper, we introduce the notions of in-, out-, and in-/out-community in order to correctly classify the directedness of the interaction of a subnetwork with the rest of the system. Furthermore, we extend the scope of community analysis by introducing the notions of in-, out-, and in-/out-pseudocommunity. They are subnetworks having strong internal connectivity but also important interactions with the rest of the system, the latter taking place by means of a minority of its nodes only. The various types of (pseudo-)communities are qualified and distinguished by a suitable set of indicators and, on a given network, they can be discovered by using a "local" searching algorithm. The application to a broad set of benchmark networks and real-world examples proves that the proposed approach is able to effectively disclose the different types of structures above defined and to usefully classify the directionality of their interactions with the rest of the system.

Stochastic fluctuations and the detectability limit of network communities

We have analyzed the detectability limits of network communities in the framework of the popular Girvan and Newman benchmark. By carefully taking into account the inevitable stochastic fluctuations that affect the construction of each and every instance of the benchmark, we come to the conclusion that the native, putative partition of the network is completely lost even before the in-degree/out-degree ratio becomes equal to that of a structureless Erdös-Rényi network. We develop a simple iterative scheme, analytically well described by an infinite branching process, to provide an estimate of the true detectability limit. Using various algorithms based on modularity optimization, we show that all of them behave (semiquantitatively) in the same way, with the same functional form of the detectability threshold as a function of the network parameters. Because the same behavior has also been found by further modularity-optimization methods and for methods based on different heuristics implementations, we conclude that indeed a correct definition of the detectability limit must take into account the stochastic fluctuations of the network construction.

Enhanced community structure detection in complex networks with partial background information

Community structure detection in complex networks is important since it can help better understand the network topology and how the network works. However, there is still not a clear and widely-accepted definition of community structure, and in practice, different models may give very different results of communities, making it hard to explain the results. In this paper, different from the traditional methodologies, we design an enhanced semi-supervised learning framework for community detection, which can effectively incorporate the available prior information to guide the detection process and can make the results more explainable. By logical inference, the prior information is more fully utilized. The experiments on both the synthetic and the real-world networks confirm the effectiveness of the framework.

Identification of unstable network modules reveals disease modules associated with the progression of Alzheimer's disease

Alzheimer's disease (AD), the most common cause of dementia, is associated with aging, and it leads to neuron death. Deposits of amyloid β and aberrantly phosphorylated tau protein are known as pathological hallmarks of AD, but the underlying mechanisms have not yet been revealed. A high-throughput gene expression analysis previously showed that differentially expressed genes accompanying the progression of AD were more down-regulated than up-regulated in the later stages of AD. This suggested that the molecular networks and their constituent modules collapsed along with AD progression. In this study, by using gene expression profiles and protein interaction networks (PINs), we identified the PINs expressed in three brain regions: the entorhinal cortex (EC), hippocampus (HIP) and superior frontal gyrus (SFG). Dividing the expressed PINs into modules, we examined the stability of the modules with AD progression and with normal aging. We found that in the AD modules, the constituent proteins, interactions and cellular functions were not maintained between consecutive stages through all brain regions. Interestingly, the modules were collapsed with AD progression, specifically in the EC region. By identifying the modules that were affected by AD pathology, we found the transcriptional regulation-associated modules that interact with the proteasome-associated module via UCHL5 hub protein, which is a deubiquitinating enzyme. Considering PINs as a system made of network modules, we found that the modules relevant to the transcriptional regulation are disrupted in the EC region, which affects the ubiquitin-proteasome system.

Significant scales in community structure

Many complex networks show signs of modular structure, uncovered by community detection. Although many methods succeed in revealing various partitions, it remains difficult to detect at what scale some partition is significant. This problem shows foremost in multi-resolution methods. We here introduce an efficient method for scanning for resolutions in one such method. Additionally, we introduce the notion of "significance" of a partition, based on subgraph probabilities. Significance is independent of the exact method used, so could also be applied in other methods, and can be interpreted as the gain in encoding a graph by making use of a partition. Using significance, we can determine "good" resolution parameters, which we demonstrate on benchmark networks. Moreover, optimizing significance itself also shows excellent performance. We demonstrate our method on voting data from the European Parliament. Our analysis suggests the European Parliament has become increasingly ideologically divided and that nationality plays no role.

Processing of natural sounds: characterization of multipeak spectral tuning in human auditory cortex

We examine the mechanisms by which the human auditory cortex processes the frequency content of natural sounds. Through mathematical modeling of ultra-high field (7 T) functional magnetic resonance imaging responses to natural sounds, we derive frequency-tuning curves of cortical neuronal populations. With a data-driven analysis, we divide the auditory cortex into five spatially distributed clusters, each characterized by a spectral tuning profile. Beyond neuronal populations with simple single-peaked spectral tuning (grouped into two clusters), we observe that ∼60% of auditory populations are sensitive to multiple frequency bands. Specifically, we observe sensitivity to multiple frequency bands (1) at exactly one octave distance from each other, (2) at multiple harmonically related frequency intervals, and (3) with no apparent relationship to each other. We propose that beyond the well known cortical tonotopic organization, multipeaked spectral tuning amplifies selected combinations of frequency bands. Such selective amplification might serve to detect behaviorally relevant and complex sound features, aid in segregating auditory scenes, and explain prominent perceptual phenomena such as octave invariance.

Shape, connectedness and dynamics in neuronal networks

The morphology of neurons is directly related to several aspects of the nervous system, including its connectedness, health, development, evolution, dynamics and, ultimately, behavior. Such interplays of the neuronal morphology can be understood within the more general shape-function paradigm. The current article reviews, in an introductory way, some key issues regarding the role of neuronal morphology in the nervous system, with emphasis on works developed in the authors' group. The following topics are addressed: (a) characterization of neuronal shape; (b) stochastic synthesis of neurons and neuronal systems; (c) characterization of the connectivity of neuronal networks by using complex networks concepts; and (d) investigations of influences of neuronal shape on network dynamics. The presented concepts and methods are useful also for several other multiple object systems, such as protein-protein interaction, tissues, aggregates and polymers.

The role of gender in scholarly authorship

Gender disparities appear to be decreasing in academia according to a number of metrics, such as grant funding, hiring, acceptance at scholarly journals, and productivity, and it might be tempting to think that gender inequity will soon be a problem of the past. However, a large-scale analysis based on over eight million papers across the natural sciences, social sciences, and humanities reveals a number of understated and persistent ways in which gender inequities remain. For instance, even where raw publication counts seem to be equal between genders, close inspection reveals that, in certain fields, men predominate in the prestigious first and last author positions. Moreover, women are significantly underrepresented as authors of single-authored papers. Academics should be aware of the subtle ways that gender disparities can occur in scholarly authorship.