betweenness: Compute betweenness centrality for an undirected graph

Description Usage Arguments Details Value Author(s) References See Also Examples

Description

Compute betweenness centrality for an undirected graph

Usage

1

Arguments

g

an instance of the graph class with edgemode “undirected”

Details

Brandes.betweenness.centrality computes the betweenness centrality of each vertex or each edge in the graph, using an algorithm by U. Brandes.

Betweenness centrality of a vertex v is calculated as follows: N_st(v) = no. of shortest paths from s to t that pass through v, N_st = no. of shortest paths from s to t, betweenness centrality of v = sum(N_st(v)/N_st) for all vertices s != v != t.

Betweenness centrality of an edge is calculated similarly.

The relative betweenness centrality for a vertex is to scale the betweenness centrality of the given vertex by 2/(n**2 - 3n + 2) where n is the no. of vertices in the graph.

Central point dominance measures the maximum betweenness of any vertex in the graph.

See documentation on brandes betweenness centrality in Boost Graph Library for more details.

Value

A list of

betweenness.centrality.vertices

betweenness centrality of each vertex

betweenness.centrality.edges

betweenness centrality of each edge

relative.betweenness.centrality.vertices

relative betweenness centrality of each vertex

dominance

maximum betweenness of any point in the graph

Author(s)

Li Long <[email protected]>

References

Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )

The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8

See Also

betweenness.centrality.clustering

Examples

1
2
3
4
5
con <- file(system.file("XML/conn.gxl",package="RBGL"), open="r")
coex <- fromGXL(con)
close(con)
coex <- ugraph(coex)
brandes.betweenness.centrality(coex)

Example output

Loading required package: graph
Loading required package: BiocGenerics
Loading required package: parallel

Attaching package: 'BiocGenerics'

The following objects are masked from 'package:parallel':

    clusterApply, clusterApplyLB, clusterCall, clusterEvalQ,
    clusterExport, clusterMap, parApply, parCapply, parLapply,
    parLapplyLB, parRapply, parSapply, parSapplyLB

The following objects are masked from 'package:stats':

    IQR, mad, xtabs

The following objects are masked from 'package:base':

    Filter, Find, Map, Position, Reduce, anyDuplicated, append,
    as.data.frame, cbind, colnames, do.call, duplicated, eval, evalq,
    get, grep, grepl, intersect, is.unsorted, lapply, lengths, mapply,
    match, mget, order, paste, pmax, pmax.int, pmin, pmin.int, rank,
    rbind, rownames, sapply, setdiff, sort, table, tapply, union,
    unique, unsplit, which, which.max, which.min

$betweenness.centrality.vertices
     A B C  D E H F G
[1,] 0 0 0 12 4 4 0 0

$edges
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,] "A"  "A"  "A"  "B"  "B"  "C"  "D"  "D"  "E"  "E"   "E"   "H"   "H"   "F"  
[2,] "B"  "C"  "D"  "C"  "D"  "D"  "E"  "H"  "G"  "H"   "F"   "F"   "G"   "G"  

$betweenness.centrality.edges
           [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13]
centrality    1    1    5    1    5    5    8    8    3     1     3     3     3
           [,14]
centrality     1

$relative.betweenness.centrality.vertices
     A B C         D         E         H F G
[1,] 0 0 0 0.5714286 0.1904762 0.1904762 0 0

$dominance
[1] 0.5170068

RBGL documentation built on May 31, 2017, 8:23 p.m.