centrality_degree_discount: DegreeDiscountIC and SingleDiscount Rankings

In cograph: Analysis and Visualization of Complex Networks

DegreeDiscountIC and SingleDiscount Rankings

Description

Chen, Wang and Yang's (2009) degree-discount heuristics for choosing spreaders under the independent-cascade model. Nodes are selected one at a time by the largest discounted degree; after each selection every unselected neighbor v of the new seed counts one more selected neighbor, t_v, and its discounted degree becomes

dd_v = d_v - 2 t_v - (d_v - t_v)\, t_v\, p

for DegreeDiscountIC (Algorithm 4 of the paper, with propagation probability p, default 0.01), or simply d_v - t_v for SingleDiscount, where each neighbor of a new seed discounts its degree by one. Every node is placed, so the result is a full ranking, returned as a score: the first node selected scores 1, the last 1 / n.

Usage

centrality_degree_discount(x, discount_p = 0.01, ...)

centrality_single_discount(x, ...)

Arguments

x	Network input (matrix, igraph, network, cograph_network, tna object).
discount_p	Propagation probability p for DegreeDiscountIC. Default 0.01.
...	Additional arguments passed to centrality.

Details

Ties are broken by node order, which the paper does not specify. Direction, edge weights and self-loops are ignored, as in the paper's setting. Validated against an independent implementation of the algorithm and against the reference code of the influence-maximization literature on the karate club graph.

Value

Named numeric vector in (0, 1], one score per node.

References

Chen, W., Wang, Y., & Yang, S. (2009). Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 199-208.

See Also

centrality_voterank for the voting-based alternative.

Examples

adj <- matrix(0, 6, 6)
adj[cbind(c(1, 1, 2, 4, 4, 5, 3), c(2, 3, 3, 5, 6, 6, 4))] <- 1
adj <- adj + t(adj)
rownames(adj) <- colnames(adj) <- LETTERS[1:6]
centrality_degree_discount(adj)
centrality_single_discount(adj)

cograph documentation built on Sept. 30, 2026, 5:08 p.m.