Computes PageRank probabilities on the graph whose vertices represent input edges, then aggregates them at the original endpoints. On directed inputs, edge e can lead to f when the target of e is the source of f. On undirected inputs, distinct edge states are adjacent when they share an endpoint, following Kosa et al.'s clarification. This uses one state per undirected edge. A pair sharing both endpoints is adjacent once.
Arguments
- x
Network input accepted by
centrality.- damping
Edge-walk continuation probability in [0,1), default 0.85.
- linerank_aggregation
Either probability (default) or weight.
- ...
Additional arguments to
centrality.
Details
Line-graph transition weights are products of original edge weights. Row normalization cancels the starting edge weight, so products need not be formed. Uniform teleportation uses probability 1-damping; a dangling edge state also redistributes uniformly. The latter is an explicit cograph PageRank convention because the source does not pin dangling behavior. Damping accepts [0,1), default 0.85; zero is a limit extension.
Default linerank_aggregation = "probability" sums stationary edge
probabilities, following the definition's prose and the later study.
Raw scores then sum to two on a graph with edges. "weight"
additionally multiplies each probability by its original edge weight,
matching the weighted incidence aggregation in Kang et al.'s Algorithm 2.
These conventions differ for weighted inputs and are not interchangeable.
The original pseudocode also has inconsistent row/column normalization;
this implementation follows its random-walk definition, corroborated by
the later paper, rather than claiming literal pseudocode equivalence.
Retains direction, loops and remaining parallel edges as distinct states.
A directed loop can transition to itself. Undirected line graphs exclude
self transitions. Both aggregation choices count endpoint incidences, so
an original loop contributes twice at its node. These loop conventions
are explicit extensions. Generic loops and simplify apply
first. Finite nonnegative weights are supported; zero-weight edges are
absent. weighted = FALSE uses unit edge weights. Generic mode,
shortest-path inversion and cutoff do not affect the result. Isolates
score zero, edgeless inputs return zeros, and empty inputs return no scores.
The native dense line-graph solve costs O(m cubed) time and O(m squared) memory for m retained edges; this is not the authors' distributed large-graph implementation. The measure must be requested explicitly. Unresolvable transition ranges, unstable systems and overflowing raw weighted aggregation raise errors. Maximum normalization supports raw weight overflow by scaling weights first; tiny ratios can underflow.
References
Kang, U., Papadimitriou, S., Sun, J., & Tong, H. (2011). Centralities in Large Networks: Algorithms and Observations. SDM, 119-130. Definitions 2-4, Algorithm 2. doi:10.1137/1.9781611972818.11 . Kosa, B., Balassi, M., Englert, P., & Kiss, A. (2015). Betweenness versus Linerank. Computer Science and Information Systems, 12(1), 33-48, section 4. doi:10.2298/CSIS141101092K .
Examples
centrality_linerank(igraph::make_ring(4))
#> 1 2 3 4
#> 0.5 0.5 0.5 0.5