CiteULike: kubyaddi's library [17 articles]

Module identification in bipartite networks with applications to directed networks

R Guimera — 2007-07-05T05:13:01-00:00

(12 Jan 2007)

Modularity is one of the most prominent properties of real-world complex networks. Here, we address the issue of module identification in an important class of networks known as bipartite networks. Nodes in bipartite networks are divided into two non-overlapping sets, and the links must have one end node from each set. We suggest a novel approach especially suited for module detection in bipartite networks, and define a set of random networks that permit the evaluation of the accuracy of the new approach. Finally, we discuss how our approach can also be used to accurately identify modules in directed unipartite networks.

Resolution limit in community detection

Santo Fortunato — 2007-02-04T14:44:48-00:00

PNAS, Vol. 104, No. 1. (2 January 2007), pp. 36-41.

Detecting community structure is fundamental for uncovering the links between structure and function in complex networks and for practical applications in many disciplines such as biology and sociology. A popular method now widely used relies on the optimization of a quantity called modularity, which is a quality index for a partition of a network into communities. We find that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. This finding is confirmed through several examples, both in artificial and in real social, biological, and technological networks, where we show that modularity optimization indeed does not resolve a large number of modules. A check of the modules obtained through modularity optimization is thus necessary, and we provide here key elements for the assessment of the reliability of this community detection method. 10.1073/pnas.0605965104

Finding and evaluating community structure in networks

MEJ Newman — 2004-11-22T00:17:30-00:00

(11 August 2003)

We propose and study a set of algorithms for discovering community structure in networks -- natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.

Community structure in directed networks

EA Leicht — 2007-10-29T21:48:55-00:00

(27 Sep 2007)

We consider the problem of finding communities or modules in directed networks. The most common approach to this problem in the previous literature has been simply to ignore edge direction and apply methods developed for community discovery in undirected networks, but this approach discards potentially useful information contained in the edge directions. Here we show how the widely used benefit function known as modularity can be generalized in a principled fashion to incorporate the information contained in edge directions. This in turn allows us to find communities by maximizing the modularity over possible divisions of a network, which we do using an algorithm based on the eigenvectors of the corresponding modularity matrix. This method is shown to give demonstrably better results than previous methods on a variety of test networks, both real and computer-generated.

From the Cover: Modularity and community structure in networks

MEJ Newman — 2006-06-07T05:40:22-00:00

PNAS, Vol. 103, No. 23. (6 June 2006), pp. 8577-8582.

Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as "modularity" over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets. 10.1073/pnas.0601602103

A Method for Solving a Bipartite-Graph Clustering Problem with Sequence Optimization

Keiu Harada — 2008-02-06T07:02:47-00:00

(2007), pp. 915-920.

Self-organization of collaboration networks

Jose Ramasco — 2006-10-26T15:14:01-00:00

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 70, No. 3. (2004)

We study collaboration networks in terms of evolving, self-organizing bipartite graph models. We propose a model of a growing network, which combines preferential edge attachment with the bipartite structure, generic for collaboration networks. The model depends exclusively on basic properties of the network, such as the total number of collaborators and acts of collaboration, the mean size of collaborations, etc. The simplest model defined within this framework already allows us to describe many of the main topological characteristics (degree distribution, clustering coefficient, etc.) of one-mode projections of several real collaboration networks, without parameter fitting. We explain the observed dependence of the local clustering on degree and the degree–degree correlations in terms of the "aging" of collaborators and their physical impossibility to participate in an unlimited number of collaborations.

Co-clustering documents and words using bipartite spectral graph partitioning

Inderjit Dhillon — 2005-04-18T02:55:50-00:00

(2001), pp. 269-274.

Both document clustering and word clustering are important and well-studied problems. By using the vector space model, a document collection may be represented as a word-document matrix. In this paper, we present the novel idea of modeling the document collection as a bipartite graph between documents and words. Using this model, we pose the clustering probliem as a graph partitioning problem and give a new spectral algorithm that simultaneously yields a clustering of documents and words. This...

Random Graph Models of Social Networks

MEJ Newman — 2005-01-21T15:41:56-00:00

We describe some new exactly solvable models of the structure of social networks, based on random graphs with arbitrary degree distributions. We give models both for simple unipartite networks, such as acquaintance networks, and bipartite networks, such as affiliation networks. We compare the predictions of our models to data for a number of real-world social networks and find that in some cases, the models are in remarkable agreement with the data, whereas in others the agreement is poorer, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.

Random graphs with arbitrary degree distributions and their applications.

ME Newman — 2004-11-22T00:17:30-00:00

Phys Rev E Stat Nonlin Soft Matter Phys, Vol. 64, No. 2 Pt 2. (August 2001)

Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.

Finding community structure in networks using the eigenvectors of matrices

MEJ Newman — 2006-06-07T20:38:54-00:00

(19 May 2006)

We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a new centrality measure that identifies those vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.

Analysis of weighted networks

MEJ Newman — 2004-11-22T00:17:30-00:00

(20 July 2004)

The connections in many networks are not merely binary entities, either present or not, but have associated weights that record their strengths relative to one another. Recent studies of networks have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighted graphs to weighted ones as well. We give a number of examples of the method, including an algorithm for detecting community structure in weighted networks and a new and simple proof of the max-flow/min-cut theorem.

Statistical Mechanics of Community Detection

Joerg Reichardt — 2006-03-28T06:59:45-00:00

(27 Mar 2006)

Starting from a general ansatz, we show how community detection can be interpreted as finding the ground state of an infinite range spin glass. Our approach applies to weighted and directed networks alike. It contains the at hoc introduced quality function from \citeReichardtPRL and the modularity $Q$ as defined by Newman and Girvan \citeGirvan03 as special cases. The community structure of the network is interpreted as the spin configuration that minimizes the energy of the spin glass with the spin states being the community indices. We elucidate the properties of the ground state configuration to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study. Further we show, how hierarchies and overlap in the community structure can be detected. Computationally effective local update rules for optimization procedures to find the ground state are given. We show how the ansatz may be used to discover the community around a given node without detecting all communities in the full network and we give benchmarks for the performance of this extension. Finally, we give expectation values for the modularity of random graphs, which can be used in the assessment of statistical significance of community structure.

Topology of evolving networks: local events and universality

Reka Albert — 2006-06-13T03:02:13-00:00

(4 May 2000)

Networks grow and evolve by local events, such as the addition of new nodes and links, or rewiring of links from one node to another. We show that depending on the frequency of these processes two topologically different networks can emerge, the connectivity distribution following either a generalized power-law or an exponential. We propose a continuum theory that predicts these two regimes as well as the scaling function and the exponents, in good agreement with the numerical results. Finally, we use the obtained predictions to fit the connectivity distribution of the network describing the professional links between movie actors.

Modularity and community structure in networks

MEJ Newman — 2006-06-06T11:38:23-00:00

(17 Feb 2006)

Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has attracted considerable recent attention. One of the most sensitive detection methods is optimization of the quality function known as "modularity" over the possible divisions of a network, but direct application of this method using, for instance, simulated annealing is computationally costly. Here we show that the modularity can be reformulated in terms of the eigenvectors of a new characteristic matrix for the network, which we call the modularity matrix, and that this reformulation leads to a spectral algorithm for community detection that returns results of better quality than competing methods in noticeably shorter running times. We demonstrate the algorithm with applications to several network data sets.

Statistical mechanics of complex networks

R Albert — 2005-11-09T11:18:59-00:00

Complex networks describe a wide range of systems in nature and society, much quoted examples including the cell...

Classes of small-world networks.

LA Amaral — 2004-11-22T00:17:30-00:00

Proc Natl Acad Sci U S A, Vol. 97, No. 21. (10 October 2000), pp. 11149-11152.

We study the statistical properties of a variety of diverse real-world networks. We present evidence of the occurrence of three classes of small-world networks: (a) scale-free networks, characterized by a vertex connectivity distribution that decays as a power law; (b) broad-scale networks, characterized by a connectivity distribution that has a power law regime followed by a sharp cutoff; and (c) single-scale networks, characterized by a connectivity distribution with a fast decaying tail. Moreover, we note for the classes of broad-scale and single-scale networks that there are constraints limiting the addition of new links. Our results suggest that the nature of such constraints may be the controlling factor for the emergence of different classes of networks.