NETWORK > SUBGROUPS > GIRVAN-NEWMAN

Contents - Index

NETWORK > SUBGROUPS > GIRVAN-NEWMAN

PURPOSE Implements the Girvan-Newman iterative algorithm for finding cohesive sugbroups.

DESCRIPTION The Girvan-Newman algorithm is an iterative process designed to identify cohesive subgroups (called community detection by the authors of the algorithm). The procedure calculates the edge betweenness centrality of all the edges and then deletes the edge or edges with the highest value. The process will eventually increase the number of weak components, these components are the cohesive subgroups and they form a partition of the original data. Each time the number of components increases we obtain a new partition, these partitions are nested and the process continues whilst the number of components is less than a user specified maximum.

PARAMETERS
Input dataset:
Name of file containing network to be analyzed. Data type: Digraph.

Output) dataset containing partitions (Default = <inputfilename>-ng)
Name of data file containing nested partitions. The vertices are in the rows and the partitions are given in the columns. These are ordered from the maximum number of groups to the minimum. The column headings specify the number of groups or clusters CX indicates a partition of X groups. In a given column vertices with the same value are are in the same cluster.

LOG FILE A clustering diagram each level corresponding to a different partition, the label gives the number of clusters at that level A '·' in row labeled i column label j indicates that vertex j is a singleton cluster at that level. An 'X' indicates that vertex j is a member of a non-trivial cluster, all other members of the cluster set are found by tracing X's along row labeled i in both directions from column j until a space is encountered in each direction.

TIMING 0(N^4).

COMMENTS

REFERENCES Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002).