| Title: | Software Tools to Quantify Structural Importance of Nodes in a Network |
|---|---|
| Description: | Provides functionality to compute various node centrality measures on networks. Included are functions to compute betweenness centrality (by utilizing Madduri and Bader's SNAP library), implementations of constraint and effective network size by Burt (2000) <doi:10.1016/S0191-3085(00)22009-1>; algorithm to identify key players by Borgatti (2006) <doi:10.1007/s10588-006-7084-x>; and the bridging algorithm by Valente and Fujimoto (2010) <doi:10.1016/j.socnet.2010.03.003>. On Unix systems, the betweenness, Key Players, and bridging implementations are parallelized with OpenMP, which may run faster on systems which have OpenMP configured. |
| Authors: | Simon Jacobs [aut], Aditya Khanna [aut, cre], Kamesh Madduri [ctb], David Bader [ctb] |
| Maintainer: | Aditya Khanna <[email protected]> |
| License: | GPL-2 |
| Version: | 0.1.6 |
| Built: | 2024-11-12 05:26:35 UTC |
| Source: | https://github.com/khanna-lab/influencer |
The Betweenness centrality score of a node u is the sum over all pairs s,t of the proportion of shortest paths between s and t that pass through u. This function allows the use of either the SNAP betweenness implementation (default), or the igraph betweenness function. The SNAP version makes use of OpenMP for parallelization, and may be faster in some circumstances.
betweenness(g, snap = T)betweenness(g, snap = T)
g |
The igraph object to analyze |
snap |
True to use the SNAP betweenness code, False to use igraph::betweenness |
A numeric vector with the betweenness centrality score for each vertex
https://snap-graph.sourceforge.net/
ig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object betweenness(ig.ex) # betweenness scores for each node in the graphig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object betweenness(ig.ex) # betweenness scores for each node in the graph
Edges that reduces distances in a network are important structural bridges. Here we implement Valente and Fujimoto's metric, where a node's bridging score is the average decrease in cohesiveness if each of its edges were removed from the graph.
bridging(g)bridging(g)
g |
The igraph object to analyze. |
A numeric vector with the bridging score for each vertex
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2889704/
ig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object bridging(ig.ex) # bridging scores for each node in the graphig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object bridging(ig.ex) # bridging scores for each node in the graph
The igraph package provides an implementation of Constraint; this is an alternate implementation.
constraint(g, v = igraph::V(g))constraint(g, v = igraph::V(g))
g |
The igraph object to analyze. |
v |
vertices over which to compute constraint (default to all) |
A numeric vector with the constraint score for each vertex in v
ig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object constraint(ig.ex) # constraint scores for each node in the graphig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object constraint(ig.ex) # constraint scores for each node in the graph
The first column should be sources, the second should be targets.
csv.to.igraph(fname)csv.to.igraph(fname)
fname |
A filename |
An igraph graph object built from the filename.
## Not run: ig.csv <- csv.to.igraph("edgelist.csv")## Not run: ig.csv <- csv.to.igraph("edgelist.csv")
Burt's Effective Network Size and Constraint index. The next two functions below provide ways to measure the actors' access to structural holes in a network. Structural holes "provide opportunities to broker connections between people" (Burt 2008).
ens(g)ens(g)
g |
The igraph object to analyze. |
A numeric vector with the effective network size for each vertex
https://www.sciencedirect.com/science/article/abs/pii/S0378873397000038
ig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object ens(ig.ex) # Effective Network Size scores for each node in the graphig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object ens(ig.ex) # Effective Network Size scores for each node in the graph
The influenceR package includes functions to quantify the structural importance of nodes in a network. Algorithms include Betweenness Centrality, Bridging, Constraint Index, Effective Network Size, and Key Players. Currently, algorithms are only guaranteed to work on undirected graphs; work on directed graphs is in progress. These functions run on graph objects from the igraph package.
In addition to igraph, this package makes use of the SNAP framework for a high-performance graph data structure and an OpenMP-parallelized implementation of Betweenness Centrality. See https://snap-graph.sourceforge.net
Development of this software package was supported by NIH grant R01 DA033875.
The website and source code is located at https://github.com/khanna-lab/influenceR.
_PACKAGE
The "Key Player" family of node importance algorithms (Borgatti 2006) involves the selection of a metric of node importance and a combinatorial optimization strategy to choose the set S of vertices of size k that maximize that metric.
keyplayer(g, k, prob = 0, tol = 1e-04, maxsec = 120, roundsec = 30)keyplayer(g, k, prob = 0, tol = 1e-04, maxsec = 120, roundsec = 30)
g |
The igraph object to analyze. |
k |
The size of the KP-set |
prob |
probability of accepting a state with a lower value |
tol |
tolerance within which to stop the optimization and accept the current value |
maxsec |
The total computation budget for the optimization, in seconds |
roundsec |
Number of seconds in between synchronizing workers' answer |
This function implements KPP-Pos, a metric intended to identify k nodes which optimize resource diffusion through the network. We sum over all vertices not in S the reciprocal of the shortest distance to a vertex in S.
According to Borgatti, a number of off-the-shelf optimization algorithms may be suitable to find S, such as tabu-search, K-L, simulated annealing, or genetic algorithms. He presents a simple greedy algorithm, which we excerpt here:
Select k nodes at random to populate set S
Set F = fit using appropriate key player metric.
For each node u in S and each node v not in S:
DELTAF = improvement in fit if u and v were swapped
Select pair with largest DELTAF
If DELTAF <= [tolerance] then terminate
Else, swap pair with greatest improvement in fit and set F = F + DELTAF
Go to step 3.
Our implementation uses a different optimization method which we call stochastic gradient descent. In tests on real world data, we found that our method discovered sets S with larger fits in less computation time. The algorithm is as follows:
Select k nodes at random to populate set S
Set F = fit using appropriate key player metric (KPP-Pos in our case)
Get a new state:
Pick a random u in S and v not in S.
F' = fit if u and v were swapped
If F' > F, swap u and v in S. Else, repeat step 3. (Alternatively, if a positive value is given for the ‘prob’ parameter, a swap will be accepted with a small probability regardless of whether it improves the fit).
If F' - F < tolerance or our maximum computation time is exceeded, return S. Else, go to step 3.
This implementation uses OpenMP (if available on the host system) so that multiple workers can explore the solution space in parallel. After a given of time, the workers synchronize their sets S to the one which maximizes the metric.
a vector with the vertex number of each vertex in the selected set S.
https://link.springer.com/article/10.1007/s10588-006-7084-x
ig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object keyplayer(ig.ex, k=10) # key-player set consisting of 10 actorsig.ex <- igraph::erdos.renyi.game(100, p.or.m=0.3) # generate an undirected 'igraph' object keyplayer(ig.ex, k=10) # key-player set consisting of 10 actors