centrality_dil: Degree and Importance of Lines
In cograph: Analysis and Visualization of Complex Networks

centrality_dil

R Documentation

Degree and Importance of Lines

Description

Liu, Xiong, Shi, Shi and Wang rank a node by its degree plus the share it can claim of the importance of the lines that touch it. A line matters when its two endpoints reach far beyond it and when no triangle offers a way round it, so the importance of the line e_{mn} is I_{e_{mn}}=U/\lambda with U=(k_m-p-1)(k_n-p-1) and \lambda=p/2+1, where p is the number of triangles one of whose edges is e_{mn}. That importance is then split between the endpoints in proportion to their own degrees, W_{v_iv_j}=I_{e_{ij}}(k_i-1)/(k_i+k_j-2), and the score is L_{v_i}=k_i+\sum_{v_j\in\Gamma_i}W_{v_iv_j} over the open neighborhood \Gamma_i. The measure is strictly two-hop local: only the degrees of a node, of its neighbors and the triangles on its incident lines enter, so it costs O(n\langle k\rangle^2) and its raw scores are component-local.

Usage

centrality_dil(x, ...)

Arguments

`x`	Network input accepted by `centrality`.
`...`	Additional arguments to `centrality`.

Details

\lambda is p/2+1, and reading it from a text layer gets it wrong. The stacked fraction extracts from the published PDF as \lambda=2p+1, in Liu et al.'s original as much as in the Almasi and Hu (2019) reproduction of it. The page image shows p over 2; so does the paper's own worked example, in printed prose, on page 210: for the seven-line network of its Fig. 1(b) it writes p=1, U=4, "\lambda=1/2+1=1.5" and I_{e_{45}}=4/1.5\approx 2.6667. The wrong reading returns 4/3 there. cograph reproduces 8/3.

U is never negative, so a score never falls below the node's degree. For a line (i,j), j belongs to N(i) but to neither N(j) nor the intersection, so p=|N(i)\cap N(j)|\le k_i-1 and both factors of U are at least zero. Since \lambda\ge 1, every I and every W is at least zero and L_{v_i}\ge k_i. Equality is common rather than exceptional: every line of a complete graph, of a star, or of any network whose lines all touch a degree-one node has U=0, so K_n scores n-1 at every node and a star scores its degree at every node.

The importance of a line is conserved when it is split. The two shares (k_i-1)/(k_i+k_j-2) and (k_j-1)/(k_i+k_j-2) sum to one, so \sum_i (L_{v_i}-k_i)=\sum_{e}I_e: the network's total excess over degree is exactly the total importance of its lines. That identity is asserted over the package's whole verification collection.

An isolated K_2 is the one undefined split, and it is resolved rather than refused. The denominator k_i+k_j-2 vanishes only when k_i=k_j=1, since both endpoints of a line have degree at least one – that is a two-node component – and there p=0 and U=(1-0-1)(1-0-1)=0, so the importance being divided is exactly zero while the split of it is 0/0. Because W is a share of I, and the two shares sum to one wherever they are defined, every admissible split of an exactly zero importance gives an exactly zero contribution: the answer does not depend on resolving the indeterminacy. cograph therefore writes the share as zero, taking the test before the division so that no 0/0 is ever evaluated, and both nodes of a K_2 score 1. The source says nothing about this case; the choice is cograph's, and it follows the precedent of centrality_lhc, whose 0/0 on a triangle-free graph is likewise written as zero because the denominator vanishes exactly where every numerator does. It deliberately does not follow centrality_iec, which returns NA on reducible input: there the closed form returns a finite number in place of an infinite one, so a value would be wrong, where here every candidate value is the same value.

Direction and weights are dropped, because the authors exclude them. Page 210 opens the derivation with "we assume that a network G=(V,E) is an undirected and unweighted network", and every quantity in the three equations is a count: a degree, a triangle census, a difference of integers. A directed, weighted or multigraph input is therefore projected onto its simple undirected skeleton – arcs symmetrized, weights and parallel edges collapsed to a single line, loops dropped – rather than refused, which is the convention every other undirected-domain measure in centrality already follows, and the projection is silent rather than warned for the same reason. There is no in/out/all reading to choose between, so the measure sits in the no-mode family and cutoff and invert_weights are ignored as well. The source states no normalization, so normalized = TRUE max-scales the finished vector as elsewhere in centrality.

Isolates, singletons and disconnected input need no special rule. An isolate has degree zero and an empty sum, so it scores zero; the single node of a one-node graph and every node of an edgeless graph score zero for the same reason, and an empty graph returns no scores. Because nothing in equations (1)-(3) reaches past a node's second neighbors, the raw scores are component-local: attaching a disjoint component leaves every existing score unchanged.

The source prints three numerical fixtures and all three are reproduced. Fig. 1 on page 210 prints I_{e_{45}}=9 at p=0 and 8/3 at p=1; Fig. 2 on page 211 prints L_{v_2}=26/9 and L_{v_5}=52/15 on a 27-node tree; and Table 3 on page 217 prints a DIL value for every one of the 21 nodes of the ARPA network, whose topology is Fig. 6 on the same page. All 21 printed values are reproduced, and the edge list read off the figure is corroborated independently by the paper's own degree column. See the batch 50 published audit in the package's verification directory.

Value

Named numeric vector in input node order, one score per node, each at least the node's degree in the simple undirected skeleton.

References

Liu, J., Xiong, Q., Shi, W., Shi, X. and Wang, K. (2016). Evaluating the importance of nodes in complex networks. Physica A: Statistical Mechanics and its Applications, 452, 209-219. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1016/j.physa.2016.02.049")}.

Examples


# Every line of a complete graph is shortcut by n - 2 triangles, so U is
# zero throughout and the score is the degree.
centrality_dil(igraph::make_full_graph(5))

# A triangle-free k-regular graph scores k + k(k-1)^2/2 at every node:
# 3 for a ring and 9 for the Petersen graph.
centrality_dil(igraph::make_ring(6))

# The path 1-2-3-4-5 scores 1, 2.5, 3, 2.5, 1: a line to a leaf carries
# no importance, and the two interior lines carry one each, split evenly.
centrality_dil(igraph::make_graph(c(1, 2, 2, 3, 3, 4, 4, 5),
                                  directed = FALSE))

# A triangle on two degree-three nodes is the case that needs
# lambda = p/2 + 1: I = 1 / 1.5 = 2/3, split evenly, so the two hubs
# score 3 + 1/3. Reading lambda as 2p + 1 would give 3 + 1/6.
centrality_dil(igraph::make_graph(c(1, 2, 1, 3, 2, 3, 1, 4, 2, 5),
                                  directed = FALSE))

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