Biomedical subjects

M Girvan

Publications and source records attributed to M Girvan.

3 recordsLinked to original sources

PubMed2004

Finding and evaluating community structure in networks.

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 any 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.

Journal Article↗

PubMed2002

Community structure in social and biological networks.

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that 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 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 the method 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.

Algorithms↗

PubMed2001

Structure of growing social networks.

We propose some simple models of the growth of social networks, based on three general principles: (1). meetings take place between pairs of individuals at a rate that is high if a pair has one or more mutual friends and low otherwise; (2). acquaintances between pairs of individuals who rarely meet decay over time; (3). there is an upper limit on the number of friendships an individual can maintain. Using computer simulations, we find that models that incorporate all of these features reproduce many of the features of real social networks, including high levels of clustering or network transitivity and strong community structure in which individuals have more links to others within their community than to individuals from other communities.

Journal Article↗