edge.betweenness.community: Community structure detection based on edge betweenness

Description

Many networks consist of modules which are densely connected themselves but sparsely connected to other modules.

Usage

edge.betweenness.community (graph, directed = TRUE,
    edge.betweenness = TRUE, merges = TRUE, bridges = TRUE,
    labels = TRUE)
edge.betweenness.community.merges (graph, edges)

Arguments

graph

The graph to analyze.

directed

Logical constant, whether to calculate directed edge betweenness for directed graphs. It is ignored for undirected graphs.

edge.betweenness

Logical constant, whether to return the edge betweenness of the edges at the time of their removal.

merges

Logical constant, whether to return the merge matrix representing the hierarchical community structure of the network. This argument is called merges, even if the community structure algorithm itself is divisive and not agglomerat

bridges

Logical constant, whether to return a list the edge removals which actually splitted a component of the graph.

labels

Logical constant, whether to contain the labels of the vertices in the result. More precisely, if the graph has a vertex attribute valled name, it will be part of the result object.

edges

Numeric vector, the ids of the edges to be removed from a graph, all edges should be present in the vector, their order specifies the order of removal.

Value

A named list is returned by edge.betweenness.community, with the following components:
removed.edgesNumeric vector, the edges of the graph, in the order of their removal.
edge.betweennessNumeric vector, the edge betweenness value of the removed edges, the order is the same as in removed.edges.
mergesMatrix containing the merges (ie. divisions) the algorithm performed, see the merges argument for the format.
bridgesNumeric vector, the steps (ie. edge removals) which resulted a split of a component in the graph.
labelsThe name argument of the vertices.
Note that some components may be missing or NULL if you do not request them, see the parameters.
A numeric matrix is returned by edge.betweenness.community.merges. The matrix has two column and its format is the same as the merges slot of the result of edge.betweenness.community.

concept

Edge betweenness
Community structure

Details

The edge betweenness score of an edge measures the number of shortest paths through it, see edge.betweenness for details. The idea of the edge betweenness based community structure detection is that it is likely that edges connecting separate modules have high edge betweenness as all the shortest paths from one module to another must traverse through them. So if we gradually remove the edge with the highest edge betweenness score we will get a hierarchical map, a rooted tree, called a dendrogram of the graph. The leafs of the tree are the individual vertices and the root of the tree represents the whole graph.

edge.betweenness.community performs this algorithm by calculating the edge betweenness of the graph, removing the edge with the highest edge betweenness score, then recalculating edge betweenness of the edges and again removing the one with the highest score, etc.

edge.betweeness.community returns various information collected throught the run of the algorithm. See the return value down here.

edge.betweenness.community.merges gets a list of edges and by gradually removes them from the graph it creates a merge matrix similar to the one returned by edge.betweenness.community.

References

M Newman and M Girvan: Finding and evaluating community structure in networks, Physical Review E 69, 026113 (2004)

Examples

Run this code

g <- barabasi.game(100,m=2)
eb <- edge.betweenness.community(g)

g <- graph.full(10) %du% graph.full(10)
g <- add.edges(g, c(0,10))
eb <- edge.betweenness.community(g)
E(g) [ eb$removed.edges[1] ]

Run the code above in your browser using DataLab