keyplayer: Compute a KPP-Pos set for a given graph.

In influenceR: Software Tools to Quantify Structural Importance of Nodes in a Network

Compute a KPP-Pos set for a given graph.

Description

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.

Usage

keyplayer(g, k, prob = 0, tol = 1e-04, maxsec = 120, roundsec = 30)

Arguments

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

Details

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:

1. Select k nodes at random to populate set S

2. Set F = fit using appropriate key player metric.

3. For each node u in S and each node v not in S:

   • DELTAF = improvement in fit if u and v were swapped

4. Select pair with largest DELTAF

   • If DELTAF <= [tolerance] then terminate

   • Else, swap pair with greatest improvement in fit and set F = F + DELTAF

5. 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:

1. Select k nodes at random to populate set S

2. Set F = fit using appropriate key player metric (KPP-Pos in our case)

3. 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).

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

Value

a vector with the vertex number of each vertex in the selected set S.

References

https://link.springer.com/article/10.1007/s10588-006-7084-x

Examples

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 actors

influenceR documentation built on May 31, 2023, 5:47 p.m.