L1cent: L1 Centrality/Prestige

Description

Computes L₁ centrality or L₁ prestige for each vertex. The L₁ centrality/prestige is a graph centrality/prestige measure defined for the vertices of a graph. It is (roughly) defined by (1 $-$ minimum multiplicity required for a selected vertex to become the median of the graph). For directed graphs, L₁ centrality quantifies the prominence of a vertex in making a choice and L₁ prestige quantifies the prominence of a vertex in receiving a choice. For undirected graphs, the two measures are identical.

Usage

L1cent(g, eta, mode, weight_transform)
# S3 method for igraph
L1cent(
  g,
  eta = NULL,
  mode = c("centrality", "prestige"),
  weight_transform = NULL
)
# S3 method for matrix
L1cent(
  g,
  eta = NULL,
  mode = c("centrality", "prestige"),
  weight_transform = NULL
)
# S3 method for L1cent
print(x, ...)
# S3 method for L1cent
plot(x, y = NULL, add = FALSE, ...)
# S3 method for L1cent
summary(object, ...)

Value

L1cent() returns an object of class L1cent. It is a numeric vector whose length is equivalent to the number of vertices in the graph g. Each component of the vector is the L₁ centrality (if mode = "centrality") or the L₁ prestige (if mode = "prestige") of each vertex in the given graph.

print.L1cent() prints L₁ centrality or L₁ prestige values and returns them invisibly.

plot.L1cent() draws a Lorenz curve (the group heterogeneity plot) and returns an invisible copy of a Gini coefficient (the group heterogeneity index) if argument y is not supplied. Otherwise, it draws a scatter plot.

summary.L1cent() returns an object of class table. It is a summary of the prominence values with the five-number summary, mean, and the Gini coefficient.

Arguments

g

An igraph graph object or a distance matrix. The graph must be connected. For a directed graph, it must be strongly connected. Equivalently, all entries of the distance matrix must be finite. Here, the (i,j) component of the distance matrix is the geodesic distance from the ith vertex to the jth vertex.

eta

An optional nonnegative multiplicity (weight) vector for (vertex) weighted networks. The sum of its components must be positive. If set to NULL (the default), all vertices will have the same positive weight (multiplicity) of 1, i.e., g is treated as a vertex unweighted graph. The length of the eta must be equivalent to the number of vertices.

mode

A character string. For an undirected graph, either choice gives the same result.

centrality (the default): L₁ centrality (prominence of each vertex in terms of making a choice) is used for analysis.
prestige: L₁ prestige (prominence of each vertex in terms of receiving a choice) is used for analysis.

weight_transform

An optional function to transform the edge weights when g is an igraph object and an edge weight attribute exists. This argument is ignored when g is a distance matrix.

x

An L1cent object, obtained as a result of the function L1cent().

...

Further arguments passed to or from other methods.

y

An optional argument providing the coordinates for a scatter plot. It could be an object of class L1cent or L1centLOC, or a numeric vector.

add

A logical value. This argument is considered only when drawing a Lorenz curve.

TRUE: add the Lorenz curve to an already existing plot.
FALSE (the default): draw the Lorenz curve to a new graphic device.

object

An L1cent object, obtained as a result of the function L1cent().

Details

Suppose that g is a (strongly) connected graph consisting of n vertices v₁, ..., v_n whose multiplicities (weights) are $\eta_1,\dots,\eta_n \geq 0$, respectively, and $\eta_{\cdot} = \sum_{k=1}^n \eta_k > 0$.

The centrality median vertex of this graph is the node minimizing the weighted sum of distances. That is, v_i is the centrality median vertex if $$ \sum_{k=1}^{n} \eta_k d(v_i, v_k) $$ is minimized, where $d(v_i,v_k)$ denotes the geodesic (shortest path) distance from $v_i$ to $v_k$. See igraph::distances() for algorithms for computing geodesic distances between vertices. When the indices are swapped to $d(v_k, v_i)$ in the display above, we call the node minimizing the weighted sum as the prestige median vertex. When the graph is undirected, the prestige median vertex and the centrality median vertex coincide, and we call it the graph median, following Hakimi (1964).

The L₁ centrality for an arbitrary node v_i is defined as ‘one minus the minimum weight that is required to make it a centrality median vertex.’ This concept of centrality is closely related to the data depth for ranking multivariate data, as defined in Vardi and Zhang (2000). It turns out that the following formula computes the L₁ centrality for the vertex v_i: $$ 1-\mathcal{S}(\texttt{g})\max_{j\neq i}\left\{\frac{\sum_{k=1}^{n}\eta_k (d(v_i,v_k) - d(v_j,v_k)) }{\eta_{\cdot}d(v_j,v_i)}\right\}^{+}, $$ where $\{\cdot\}^{+}=\max(\cdot,0)$ and $\mathcal{S}(\texttt{g}) = \min_{i\neq j} d(v_i,v_j)/d(v_j,v_i)$. The L₁ centrality of a vertex is in $[0,1]$ by the triangle inequality, and the centrality median vertex has centrality 1. The L₁ prestige is defined analogously, with the indices inside the distance function swapped.

For an undirected graph, $\mathcal{S}(\texttt{g}) = 1$ since the distance function is symmetric. Moreover, L₁ centrality and L₁ prestige measures concide.

For details, refer to Kang and Oh (2025a) for undirected graphs, and Kang and Oh (2025b) for directed graphs.

References

S. L. Hakimi. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3):450--459, 1964.

S. Kang and H.-S. Oh. On a notion of graph centrality based on L₁ data depth. Journal of the American Statistical Association, 1--13, 2025a.

S. Kang and H.-S. Oh. L₁ prominence measures for directed graphs. The American Statistician, 1--16, 2025b.

Y. Vardi and C.-H. Zhang. The multivariate L₁-median and associated data depth. Proceedings of the National Academy of Sciences, 97(4):1423--1426, 2000.

Examples

Run this code

# igraph object and distance matrix as an input lead to the same result
vertex_weight <- igraph::V(MCUmovie)$worldwidegross
cent_igraph <- L1cent(MCUmovie, eta = vertex_weight)
cent_matrix <- L1cent(igraph::distances(MCUmovie), eta = vertex_weight)
all(cent_igraph == cent_matrix)

# Top 6 vertices with the highest L1 centrality
utils::head(sort(cent_igraph, decreasing = TRUE))

# Lorenz curve
plot(cent_igraph)

# Summary statistics
summary(cent_igraph)

Run the code above in your browser using DataLab