CiteULike: bigbossman's structure

Community Structure in the United States House of Representatives

Mason Porter — 2006-10-21T03:59:31-00:00

(4 Feb 2006)

We investigate the networks of committee and subcommittee assignments in the United States House of Representatives from the 101st--108th Congresses, with committees connected according to “interlocks” or common membership. We examine the House's community structure using several methods, which reveal strong links between different committees as well as the intrinsic hierarchical structure within the House as a whole. We identify structural changes, including additional hierarchical levels and higher modularity, resulting from the 1994 elections, in which the Republican party earned majority status in the House for the first time in more than forty years. We also combine our network approach with analysis of roll call votes using singular value decomposition to uncover correlations between the political and organizational structure of House committees.

Feature-based similarity search in graph structures

Xifeng Yan — 2007-01-05T02:29:30-00:00

ACM Trans. Database Syst., Vol. 31, No. 4. (December 2006), pp. 1418-1453.

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.

Fast algorithm for detecting community structure in networks

MEJ Newman — 2005-02-15T17:25:06-00:00

(22 September 2003)

It has been found that many networks display community structure -- groups of vertices within which connections are dense but between which they are sparser -- and highly sensitive computer algorithms have in recent years been developed for detecting such structure. These algorithms however are computationally demanding, which limits their application to small networks. Here we describe a new algorithm which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster than previous algorithms. We give several example applications, including one to a collaboration network of more than 50000 physicists.

Finding community structure in very large networks

Aaron Clauset — 2005-02-15T17:26:15-00:00

(30 August 2004)

The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in which case our algorithm runs in essentially linear time, O(n log^2 n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web-site of a large online retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400,000 vertices and 2 million edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.

Community structure identification

Leon Danon — 2006-09-15T21:43:53-00:00

(18 Oct 2005)

We review and compare recent approaches to community structure identification. Definitions of communities are revisited, as well as the recently proposed modularity measure. We then classify the various methods into link removal methods, agglomerative methods, methods based on optimising the modularity measure, spectral methods and others. Finally, the performance of the methods, as applied to ad-hoc networks with known community structre, is compared. The work is intended as an overview and introduction into community structure identification in complex networks.

Community structure in social and biological networks

Michelle Girvan — 2005-09-30T09:22:46-00:00

(7 Dec 2001)

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the World-Wide Web. Researchers have concentrated particularly on a few properties which seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this paper, we highlight another property which is found in many networks, the property of community structure, in which network nodes are joined together in tightly-knit groups between which there are only looser connections. We propose a new method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer generated and real-world graphs whose community structure is already known, and find that it detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well-known - a collaboration network and a food web - and find that it detects significant and informative community divisions in both cases.

The skip quadtree: a simple dynamic data structure for multidimensional data

David Eppstein — 2006-04-30T08:58:01-00:00

(2005), pp. 296-305.