betaFeedback

WorksComputer Science

Theoretical relations between basic centrality measures in real-world networks

Abstract

We establish new relationships among several fundamental measures of real-world networks, including the average clustering coefficient, the global clustering coefficient, the average shortest-path length and degree centrality, closeness centrality, betweenness centrality and ksi-centrality. We further develop the theory of jj-neighborhood centrality, which encompasses degree centrality and ksi-centrality as special cases.

Introduction

The structural analysis of complex networks is one of the central topics in modern graph theory and network science. Understanding the structure of networks in real-world systems requires the use of quantitative characteristics that capture different aspects of vertex importance, local connectivity, clustering, and global distances.

One of the most widely used structural characteristics are vertex centrality measures. Centrality measures describe the importance of vertices from different perspectives, such as the number of direct connections, the ability to mediate communication between other vertices, or the proximity to the remaining vertices of the network. A wide variety of centrality measures have been proposed in a network science. For example, Shvydun [1] described more than 200 known centrality measures, while his website currently lists over 400. Some of the most widely used centrality measures include degree centrality, local clustering, closeness centrality, and betweenness centrality. The systematic study of these concepts in social network analysis goes back to the classical works of Freeman[2, 3].

In real-world networks (constructed from empirical data) the most important characteristics are degree distribution, ksi-distribution, the average clustering coefficient, and the average shortest-path length. The average shortest-path length is one of the key measures used to characterize the small-world properties of a network, whereas the average clustering coefficient reflects the density of connections among neighboring vertices and thus the tendency of the network to form tightly connected communities [4]. Another direction concerns the distributions of degree centrality and ksi-centrality. The skewnesses of these distributions are invariants of real networks and distinguish real-world networks from artificially generated ones. In [5], the author showed that degree centrality and ksi-centrality can be unified within a single sequence of centrality measures called jj-neighborhood centralities. In this context, Laplacian-based jj-neighborhood centralities offer an additional approach to describing the local structure of a graph. In particular, the ksi-centrality considered in this work is defined through the Laplacian quadratic form evaluated at the characteristic vector of the open neighborhood of a vertex.

This article builds on the author’s earlier efforts, presented in [6, 7], to establish rigorous combinatorial proofs of the relationships between various centrality measures and other graph invariants, and further develops this line of research. In this article we generalized results about the relation between average clustering coefficient and global clustering coefficient, and obtained a new relation between average clustering coefficient and average shortest path length for any graph. In addition, we found many new relations between these values, another centralities and jj-neighborhood centralities (including degree and ksi-centralities).

J-neighborhood centrality and its properties

Here we propose new relations of jj-neighborhood centrality from [5]. This centrality is a set of centralities ξij\xi_i^j for a vertex ii parametrized by jj:

ξij=(Lχij,χij)(χij,χij)\xi_i^j = \frac{\left(L\chi_i^j,\chi_i^j\right)}{\left(\chi_i^j,\chi_i^j\right)}

where χij(k)\chi_i^j(k) is the characteristic function of Nj(i)\mathcal{N}^j(i), that is

χij(k)={1,k∈Nj(i),0,otherwise.\chi_i^j(k) = \begin{cases} 1, & k \in\mathcal{N}^j(i),\\ 0, & \text{otherwise}. \end{cases}

For j=0j=0 and 11 this centrality coincides with degree and ksi-centrality respectively. For larger jj the skewness of its distribution is a new invariant of real networks, that differentiates real networks from synthetic ones. Let’s use the notations of jj-neighborhood Nj(i)\mathcal{N}^j(i) of a vertex ii and of the set of edges E(A,B)E(A,B) from the set AA to BB from [5].

Lemma 1. Let’s fix some vertex ii. For jj-neighborhood centrality holds

ξij={number of shortest paths from i to all vertices of length j}+{the same of length j+1}∣Nj(i)∣\xi_i^j = \frac{\{\text{number of shortest paths from }i\text{ to all vertices of length }j\}+\{\text{the same of length }j+1\}}{|\mathcal{N}^j(i)|}
1+∣Nj+1(i)∣∣Nj(i)∣≤ξij≤∣Nj−1(i)∣+∣Nj+1(i)∣.1+\frac{|\mathcal{N}^{j+1}(i)|}{|\mathcal{N}^j(i)|}\leq\xi_i^j \leq|\mathcal{N}^{j-1}(i)|+|\mathcal{N}^{j+1}(i)|.

Proof. Let’s note, that

ξij∣Nj(i)∣=E(Nj(i),V∖Nj(i))=E(Nj−1(i),Nj(i))+E(Nj(i),Nj+1(i)).\xi_i^j|\mathcal{N}^j(i)|=E(\mathcal{N}^j(i),V\setminus\mathcal{N}^j(i))=E(\mathcal{N}^{j-1}(i),\mathcal{N}^j(i))+E(\mathcal{N}^j(i),\mathcal{N}^{j+1}(i)).

The first holds the fact, that there is a bijection between the number of shortest paths from ii to all vertices of length jj and edges of E(Nj−1(i),Nj(i))E(\mathcal{N}^{j-1}(i),\mathcal{N}^j(i)).

The second holds from two facts: the maximum number of edges E(Nj−1(i),Nj(i))E(\mathcal{N}^{j-1}(i),\mathcal{N}^j(i)) is ∣Nj−1(i)∣⋅∣Nj(i)∣|\mathcal{N}^{j-1}(i)|\cdot|\mathcal{N}^j(i)| and for any vertex of Nj(i)\mathcal{N}^j(i) there exists a least one adjacent edge from E(Nj−1(i),Nj(i))E(\mathcal{N}^{j-1}(i),\mathcal{N}^j(i)). Therefore, holds

∣Nj(i)∣≤E(Nj−1(i),Nj(i))≤∣Nj−1(i)∣⋅∣Nj(i)∣.|\mathcal{N}^j(i)|\leq E(\mathcal{N}^{j-1}(i),\mathcal{N}^j(i))\leq|\mathcal{N}^{j-1}(i)|\cdot|\mathcal{N}^j(i)|.

The same for E(Nj(i),Nj+1(i))E(\mathcal{N}^j(i),\mathcal{N}^{j+1}(i)).

This lemma allows us to define normalized versions of jj-neighborhood centralities in two different ways:

  1. the first way

ξ^ij=E(Nj(i),V∖Nj(i))∣Nj(i)∣(∣Nj−1(i)∣+∣Nj+1(i)∣)\hat{\xi}_i^j=\frac{E(\mathcal{N}^j(i),V\setminus\mathcal{N}^j(i))}{|\mathcal{N}^j(i)|\left(|\mathcal{N}^{j-1}(i)|+|\mathcal{N}^{j+1}(i)|\right)}
  1. and the second

ξij=E(Nj(i),V∖Nj(i))∣Nj(i)∣(n−∣Nj(i)∣)\xi_i^j=\frac{E(N^j(i),V\setminus N^j(i))}{|N^j(i)|(n-|N^j(i)|)}

since ∣Nj−1(i)∣+∣Nj+1(i)∣≤n−∣Nj(i)∣|N^{j-1}(i)|+|N^{j+1}(i)|\le n-|N^j(i)|, where nn is the number of nodes. Note that in [?] the second approach is used.

Lemma 2. Let ii be a vertex of a simple undirected graph:

∑t∈V(G)dist⁡(i,t)≥∑j=1kj(ξij−1)(ξij−1−1)⋯(ξi1−1),where k=1,2,…,e(i),\sum_{t\in V(G)}\operatorname{dist}(i,t)\ge\sum_{j=1}^{k}j(\xi_i^j-1)(\xi_i^{j-1}-1)\cdots(\xi_i^1-1),\quad\text{where }k=1,2,\ldots,e(i),
∑t∈V(G)dist⁡(i,t)≤D(n−1)−∑j=1k(D−j)(ξij−1−(ξij−3−1)(ξij−4−1)⋯(ξi1−1)ξi0ξi−1),\sum_{t\in V(G)}\operatorname{dist}(i,t)\le D(n-1)-\sum_{j=1}^{k}(D-j)\left(\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\cdots(\xi_i^1-1)\xi_i^0\xi_i^{-1}\right),

where k=1,2,…,min⁡(e(i),D−1)k=1,2,\ldots,\min(e(i),D-1), ξi−1=1\xi_i^{-1}=1, and

ξij−1−(ξij−3−1)(ξij−4−1)⋯(ξi1−1)ξi0ξi−1={ξi0,for j=1,ξi1−ξi−1,for j=2,ξi2−ξi0ξi−1,for j=3.\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\cdots(\xi_i^1-1)\xi_i^0\xi_i^{-1}= \begin{cases} \xi_i^0, & \text{for }j=1,\\ \xi_i^1-\xi_i^{-1}, & \text{for }j=2,\\ \xi_i^2-\xi_i^0\xi_i^{-1}, & \text{for }j=3. \end{cases}

Proof. Let’s note that

∑t∈V(G)dist⁡(i,t)=∑j=1Dj∣Nj(i)∣=∑j=1Dj∣Nj(i)∣+D(n−1−∑j=1D−1∣Nj(i)∣)=D(n−1)−∑j=1D−1(D−j)∣Nj(i)∣.\sum_{t\in V(G)}\operatorname{dist}(i,t)=\sum_{j=1}^{D}j|N^j(i)|=\sum_{j=1}^{D}j|N^j(i)|+D\left(n-1-\sum_{j=1}^{D-1}|N^j(i)|\right)=D(n-1)-\sum_{j=1}^{D-1}(D-j)|N^j(i)|.

Therefore,

∑j=1lj∣Nj(i)∣≤∑t∈V(G)dist⁡(i,t)≤D(n−1)−∑j=1k(D−j)∣Nj(i)∣,\sum_{j=1}^{l}j|N^j(i)|\le\sum_{t\in V(G)}\operatorname{dist}(i,t)\le D(n-1)-\sum_{j=1}^{k}(D-j)|N^j(i)|,

for l=1,2,…,e(i)l=1,2,\ldots,e(i), and k=1,2,…,min⁡(e(i),D−1)k=1,2,\ldots,\min(e(i),D-1). By the previous lemma we have

∣Nj(i)∣≤(ξij−1−1)∣Nj−1(i)∣,|N^j(i)|\le(\xi_i^{j-1}-1)|N^{j-1}(i)|,

and

∣Nj(i)∣≥ξij−1−∣Nj−2(i)∣≥ξij−1−(ξij−3−1)∣Nj−3(i)∣≥…|N^j(i)|\ge\xi_i^{j-1}-|N^{j-2}(i)|\ge\xi_i^{j-1}-(\xi_i^{j-3}-1)|N^{j-3}(i)|\ge\ldots
…≥ξij−1−(ξij−3−1)(ξij−4−1)…(ξi1−1)ξi0.\ldots\ge\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\ldots(\xi_i^1-1)\xi_i^0.

Lemma 3. For any simple graph GG and for any j=1,2,…,min⁡i∈V(G)e(i)j=1,2,\ldots,\min_{i\in V(G)}e(i),

∑i∈V(G)ξij∣Nj(i)∣≥∑i∈Nj(i)∣Nj(i)∣di−2(2j+1)C2j+1(G),\sum_{i\in V(G)}\xi_i^j|N^j(i)|\ge\sum_{i\in N^j(i)}|N^j(i)|d_i-2(2j+1)C_{2j+1}(G),

where C2j+1(G)C_{2j+1}(G) is the number of 2j+12j+1-cycles in the graph.

Proof. Let’s note that

ξij∣Nj(i)∣=∑i∈Nj(i)di−2∣E(Nj(i))∣.\xi_i^j|N^j(i)|=\sum_{i\in N^j(i)}d_i-2|E(N^j(i))|.

For a fixed ii each edge E(Nj(i))E(N^j(i)) corresponds to different 2j+12j+1-cycle in GG. Therefore, C2j+1(G)≥(2j+1)∑i∈V(G)E(Nj(i))C_{2j+1}(G)\ge(2j+1)\sum_{i\in V(G)}E(N^j(i)).

Lemma 4. For any simple graph

∑i∈V(G)∑j=0Dξij∣Nj(i)∣=2∑i∈V(G)Str⁡(i),\sum_{i\in V(G)}\sum_{j=0}^{D}\xi_i^j\lvert N^j(i)\rvert= 2\sum_{i\in V(G)}\operatorname{Str}(i),

where ∣Nj(i)∣=0\lvert N^j(i)\rvert=0, if there is no vertices k:dist⁡(i,k)=jk:\operatorname{dist}(i,k)=j.

Proof. By the lemma 1:

∑j=0Dξij∣Nj(i)∣=2{total number of shortest paths from i}.\sum_{j=0}^{D}\xi_i^j\lvert N^j(i)\rvert=2\{\text{total number of shortest paths from }i\}.

Relations for centralities important for real networks

In real networks there four important centralities which related to their structural properties. They are local clustering, radiality, degree and ksi centralities. In this section, we establish new relations between them and other centralities.

Let’s propose the requiring centralities and another characteristics for a graph GG:

  1. degree did_i, i∈V(G)i\in V(G),

  1. let’s denote si=di(di−1)s_i=d_i(d_i-1), i∈V(G)i\in V(G),

  1. local cluster coefficient ci=number of edges in N1(i)maximum possible number of edges in N1(i)=2∣E(N1(i))∣di(di−1)c_i=\dfrac{\text{number of edges in }N^1(i)}{\text{maximum possible number of edges in }N^1(i)}=\dfrac{2\lvert E(N^1(i))\rvert}{d_i(d_i-1)},

  1. average clustering coefficient CWS=1n∑i∈V(G)ci=1n∑i∈V(G)∑j,k∈V(G)aijajkakidi(di−1)C_{WS}=\dfrac{1}{n}\sum_{i\in V(G)}c_i=\dfrac{1}{n}\sum_{i\in V(G)}\dfrac{\sum_{j,k\in V(G)}a_{ij}a_{jk}a_{ki}}{d_i(d_i-1)},

  1. global clustering coefficient C=number of closed triplets in Gnumber of all triplets in G=∑i,j,k∈V(G)aijajkaki∑i∈V(G)di(di−1)C=\dfrac{\text{number of closed triplets in }G}{\text{number of all triplets in }G}=\dfrac{\sum_{i,j,k\in V(G)}a_{ij}a_{jk}a_{ki}}{\sum_{i\in V(G)}d_i(d_i-1)},

  1. vertex eccentricity e(i)=max⁡t∈V(G)d(i,t)e(i)=\max_{t\in V(G)}d(i,t),

  1. diameter D=max⁡s,t∈V(G)dist⁡(s,t)D=\max_{s,t\in V(G)}\operatorname{dist}(s,t),

  1. average shortest path length L=1n(n−1)∑s,t∈V(G):s≠tdist⁡(s,t)L=\dfrac{1}{n(n-1)}\sum_{s,t\in V(G):s\ne t}\operatorname{dist}(s,t),

  1. closeness centrality Clo⁡(i)=n−1∑t∈V(G)dist⁡(i,t)\operatorname{Clo}(i)=\dfrac{n-1}{\sum_{t\in V(G)}\operatorname{dist}(i,t)},

  1. stress Str⁡(i)=∑s,t∈V(G):s≠t≠iσst(i)\operatorname{Str}(i)=\sum_{s,t\in V(G):s\ne t\ne i}\sigma_{st}(i), where σst(i)\sigma_{st}(i) is the total number of shortest paths from ss to tt which contains vertex ii,

  1. betweenness BC⁡(i)=∑s,t∈V(G):s≠t≠iσst(i)σst\operatorname{BC}(i)=\sum_{s,t\in V(G):s\ne t\ne i}\dfrac{\sigma_{st}(i)}{\sigma_{st}}, where σst\sigma_{st} is the total number of shortest paths from ss to tt.

Theorem 1. For average and global clustering in simple undirected graph hold

C−CWS=cov⁡(s,c)E(s),C-C_{WS}=\frac{\operatorname{cov}(s,c)}{\mathbb{E}(s)},

where expected value E(s)=1n∑i∈V(G)si\mathbb{E}(s)=\dfrac{1}{n}\sum_{i\in V(G)}s_i and covariance cov⁡(s,c)=E((s−E(s))(c−E(c)))\operatorname{cov}(s,c)=\mathbb{E}\left((s-\mathbb{E}(s))(c-\mathbb{E}(c))\right).

Proof. Note that ∑j,k∈V(G)aijajkaki=sici\sum_{j,k\in V(G)}a_{ij}a_{jk}a_{ki}=s_ic_i, thus C=E(sc)/E(s)C=\mathbb{E}(sc)/\mathbb{E}(s). Therefore,

cov⁡(s,c)E(s)=E(sc)E(s)−E(c)=C−CWS.\frac{\operatorname{cov}(s,c)}{\mathbb{E}(s)}=\frac{\mathbb{E}(sc)}{\mathbb{E}(s)}-\mathbb{E}(c)=C-C_{WS}.

From this theorem we obtain

Corollary 1. For any simple undirected graph

  1. if cov⁡(s,c)>0\operatorname{cov}(s,c)>0, then C>CWSC>C_{WS},

  1. if cov⁡(s,c)<0\operatorname{cov}(s,c)<0, then C<CWSC<C_{WS}.

This corollary generalizes the result in [6], since if both ss and cc are monotonically increasing, covariance cov⁡(s,c)>0\operatorname{cov}(s,c)>0 and vice versa: if both ss and cc are monotonically decreasing, covariance cov⁡(s,c)<0\operatorname{cov}(s,c)<0.

Corollary 2. For any simple undirected graph

∣C−CWS∣≤var⁡(s)var⁡(c)E(s).\left|C-C_{WS}\right|\leq\frac{\sqrt{\operatorname{var}(s)\operatorname{var}(c)}}{\mathbb{E}(s)}.

This corollary shows that the standard deviations of ss and local clustering bound the difference between the global clustering and average clustering coefficients in graphs.

Let’s note that in the lemma 3 for the case j=1j=1 inequality becomes equality and thus we obtain corollary about a relation between ksi-centrality and the number of triangles in a graph.

Corollary 3. For any simple undirected graph GG

∑i∈V(G)ξidi=∑i∈V(G)di2−6T(G),\sum_{i\in V(G)}\xi_i d_i=\sum_{i\in V(G)}d_i^2-6T(G),

where T(G)T(G) is the number of triangles or closed triplets in GG.

This corollary shows that ksi centrality only depends on the number of triangles, if the distribution of degrees is fixed. Thus, the more triangles in a graphs with the same distribution of degrees, the more ksi-centrality. Also, the edge switching operation (see [8] for edge switching) can be used for controlling ksi centrality distribution in a graph.

Let’s use the lemma 2 to find bounds for different centralities in terms of jj-neighborhood centrality.

Corollary 4. For any simple undirected graph we have a sequence of inequalities

1.

Clo⁡(i)≥n−1D(n−1)−∑j=1min⁡(D−1,e(i))(D−j)(ξij−1−(ξij−3−1)(ξij−4−1)…(ξi1−1)ξi0ξi−1)≥…\operatorname{Clo}(i)\geq\frac{n-1}{D(n-1)-\sum_{j=1}^{\min(D-1,e(i))}(D-j)\left(\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\ldots(\xi_i^1-1)\xi_i^0\xi_i^{-1}\right)}\geq\ldots
…≥n−1D(n−1)−∑j=1k(D−j)(ξij−1−(ξij−3−1)(ξij−4−1)…(ξi1−1)ξi0ξi−1)≥…\ldots\geq\frac{n-1}{D(n-1)-\sum_{j=1}^{k}(D-j)\left(\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\ldots(\xi_i^1-1)\xi_i^0\xi_i^{-1}\right)}\geq\ldots
…≥n−1D(n−1)−(D−1)di−(D−2)ξi≥n−1D(n−1)−(D−1)di≥1D,\ldots\geq\frac{n-1}{D(n-1)-(D-1)d_i-(D-2)\xi_i}\geq\frac{n-1}{D(n-1)-(D-1)d_i}\geq\frac{1}{D},

2.

Clo⁡(i)≤n−1∑j=1e(i)j(ξij−1)(ξij−1−1)…(ξi1−1)≤…≤n−1∑j=1kj(ξij−1)(ξij−1−1)…(ξi1−1)≤…≤n−1ξi−1.\operatorname{Clo}(i)\leq\frac{n-1}{\sum_{j=1}^{e(i)}j(\xi_i^j-1)(\xi_i^{j-1}-1)\ldots(\xi_i^1-1)} \leq\ldots\leq\frac{n-1}{\sum_{j=1}^{k}j(\xi_i^j-1)(\xi_i^{j-1}-1)\ldots(\xi_i^1-1)} \leq\ldots\leq\frac{n-1}{\xi_i-1}.

In particular, we obtain a boundaries for closeness centrality in terms of diameter, ksi and degree for graphs with D≥2D \ge2:

n−1D(n−1)−(D−1)di−(D−2)ξi≤Clo⁡(i)≤n−1ξ−1.\frac{n-1}{D(n-1)-(D-1)d_i-(D-2)\xi_i} \le\operatorname{Clo}(i) \le\frac{n-1}{\xi-1}.

The next two theorems gives new upper and lower bounds on the average shortest path length in terms of averages of jj-neighborhood centralities and global clustering coefficients.

Theorem 2. For any simple undirected graph GG with D≥4D \ge4 we have a sequence of inequalities

Ξ‾1−1n−1≤L(G)≤D−(D−2)(Ξ‾1+d‾−1)+(D−3)Ξ‾2+(D−4)(Ξ‾3−d‾2+6T(G)n)n−1\frac{\overline{\Xi}^{1}-1}{n-1} \le L(G) \le D-\frac{(D-2)(\overline{\Xi}^{1}+\overline{d}-1)+(D-3)\overline{\Xi}^{2}+(D-4)\left(\overline{\Xi}^{3}-\overline{d}^{2}+\frac{6T(G)}{n}\right)}{n-1}
≤D−2d‾+(D−2)(Ξ‾1−1)+(D−3)Ξ‾2n−1≤D−(D−1)d‾+(D−2)(Ξ‾1−1)n−1≤D−(D−1)d‾n−1,\le D-\frac{2\overline{d}+(D-2)(\overline{\Xi}^{1}-1)+(D-3)\overline{\Xi}^{2}}{n-1} \le D-\frac{(D-1)\overline{d}+(D-2)(\overline{\Xi}^{1}-1)}{n-1} \le D-\frac{(D-1)\overline{d}}{n-1},

where d‾\overline{d} is the average degree, d‾2\overline{d}^{2} — mean square degree, Ξ‾j\overline{\Xi}^{j} — average jj-neighborhood coefficient and T(G)T(G) — the number of triangles in the graph. For smaller diameters D(G)=1,2,3D(G)=1,2,3 truncated sequences can be used.

Proof. Let’s use the lemma 2:

  1. L(G)=1n(n−1)∑s,t∈V(G):s≠tdist⁡(s,t)≥∑s∈V(G)(ξs−1)n(n−1)=Ξ‾1−1n−1,L(G)=\frac{1}{n(n-1)}\sum_{s,t\in V(G):s\ne t}\operatorname{dist}(s,t)\ge\frac{\sum_{s\in V(G)}(\xi_s-1)}{n(n-1)}=\frac{\overline{\Xi}^{1}-1}{n-1},

  1. L(G)≤D−∑j=11D−jn(n−1)(ξij−1−(ξij−3−1)(ξij−4−1)…(ξi1−1)ξi0ξi−1)=D−(D−1)d‾n−1,L(G)\le D-\sum_{j=1}^{1}\frac{D-j}{n(n-1)}\left(\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\ldots(\xi_i^{1}-1)\xi_i^{0}\xi_i^{-1}\right)=D-\frac{(D-1)\overline{d}}{n-1},

  1. L(G)≤D−∑j=12D−jn(n−1)(ξij−1−(ξij−3−1)(ξij−4−1)…(ξi1−1)ξi0ξi−1)=D−(D−1)d‾+(D−2)(Ξ‾1−1)n−1,L(G)\le D-\sum_{j=1}^{2}\frac{D-j}{n(n-1)}\left(\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\ldots(\xi_i^{1}-1)\xi_i^{0}\xi_i^{-1}\right)=D-\frac{(D-1)\overline{d}+(D-2)(\overline{\Xi}^{1}-1)}{n-1},

  1. L(G)≤D−∑j=13D−jn(n−1)(ξij−1−(ξij−3−1)(ξij−4−1)…(ξi1−1)ξi0ξi−1)=L(G)\le D-\sum_{j=1}^{3}\frac{D-j}{n(n-1)}\left(\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\ldots(\xi_i^{1}-1)\xi_i^{0}\xi_i^{-1}\right)=

=D−(D−1)d‾+(D−2)(Ξ‾1−1)+(D−3)(Ξ‾2−d‾)n−1=D−2d‾+(D−2)(Ξ‾1−1)+(D−3)Ξ‾2n−1,=D-\frac{(D-1)\overline{d}+(D-2)(\overline{\Xi}^{1}-1)+(D-3)(\overline{\Xi}^{2}-\overline{d})}{n-1} =D-\frac{2\overline{d}+(D-2)(\overline{\Xi}^{1}-1)+(D-3)\overline{\Xi}^{2}}{n-1},
  1. L(G)≤D−∑j=14D−jn(n−1)(ξij−1−(ξij−3−1)(ξij−4−1)…(ξi1−1)ξi0ξi−1)=L(G)\le D-\sum_{j=1}^{4}\frac{D-j}{n(n-1)}\left(\xi_i^{j-1}-(\xi_i^{j-3}-1)(\xi_i^{j-4}-1)\ldots(\xi_i^{1}-1)\xi_i^{0}\xi_i^{-1}\right)=

=D−2d‾+(D−2)(Ξ‾1−1)+(D−3)Ξ‾2+(D−4)(Ξ‾3−d‾2+6T(G)n+d‾)n−1=D−(D−2)(Ξ‾1+d‾−1)+(D−3)Ξ‾2+(D−4)(Ξ‾3−d‾2+6T(G)n)n−1.\begin{aligned} =D-\frac{2\overline{d}+(D-2)(\overline{\Xi}^{1}-1)+(D-3)\overline{\Xi}^{2}+(D-4)\left(\overline{\Xi}^{3}-\overline{d}^{2}+\frac{6T(G)}{n}+\overline{d}\right)}{n-1} \\ &=D-\frac{(D-2)(\overline{\Xi}^{1}+\overline{d}-1)+(D-3)\overline{\Xi}^{2}+(D-4)\left(\overline{\Xi}^{3}-\overline{d}^{2}+\frac{6T(G)}{n}\right)}{n-1}. \end{aligned}

Here we used the relation from the corollary 3.

By this theorem we obtain bounds for the average shortest path length for the graphs with D≥2D \ge2 in terms of diameter, average degree and average ksi-coefficient:

Ξ‾−1n−1≤L(G)≤D−(D−1)d‾+(D−2)(Ξ‾−1)n−1.\frac{\overline{\Xi}-1}{n-1}\le L(G)\le D-\frac{(D-1)\overline{d}+(D-2)(\overline{\Xi}-1)}{n-1}.

Theorem 3. For any simple undirected graph

L≥1+(1−C)E(s)(n−1)dmax⁡,L \ge1 + \frac{(1-C)\mathbb{E}(s)}{(n-1)d_{\max}},

where dmax⁡d_{\max} is the maximum degree.

Proof. Let’s use denotations as in [7]. Consider the local betweenness BC(i,N1(i))=BC(i)=∑s,t∈N1(i):s≠t≠iσst(i)σstBC(i,\mathcal{N}^{1}(i))=BC(i)=\sum_{s,t\in\mathcal{N}^{1}(i):s\ne t\ne i}\frac{\sigma_{st}(i)}{\sigma_{st}}, where shortest paths between vertices s,ts,t are calculated in the whole graph GG.

For average local betweenness holds

∑i∈V(G)BC(i,N1(i))=∑i∈V(G)∑s,t∈N1(i):(s,t)∉E(N1(i))1σst=2{number of pairs (s,t):dist⁡(s,t)=2}.\sum_{i\in V(G)}BC(i,\mathcal{N}^{1}(i))=\sum_{i\in V(G)}\sum_{\substack{s,t\in\mathcal{N}^{1}(i):\\(s,t)\notin E(\mathcal{N}^{1}(i))}}\frac{1}{\sigma_{st}}=2\{\text{number of pairs }(s,t):\operatorname{dist}(s,t)=2\}.

Note, that the number of all shortest paths between any pair of vertices on the distance two

∑s,t∈V(G):dist⁡(s,t)=2σst=∑i∈V(G)∑j∼i,k∼i:j≁k1=∑i∈V(G)di(di−1)(1−ci).\sum_{\substack{s,t\in V(G):\\\operatorname{dist}(s,t)=2}}\sigma_{st}=\sum_{i\in V(G)}\sum_{\substack{j\sim i,k\sim i:\\j\not\sim k}}1=\sum_{i\in V(G)}d_i(d_i-1)(1-c_i).

This number can be bounded

∑s,t∈V(G):dist⁡(s,t)=2σst≤dmax⁡{number of pairs (s,t):dist⁡(s,t)=2}.\sum_{\substack{s,t\in V(G):\\\operatorname{dist}(s,t)=2}}\sigma_{st}\le d_{\max}\{\text{number of pairs }(s,t):\operatorname{dist}(s,t)=2\}.

Therefore, using the relation between average shortest path length and betweenness from [9] and the relation from the theorem 1 we obtain

L=1+1n(n−1)∑i∈V(G)BC(i)≥1+1n(n−1)∑i∈V(G)BC(i,N1(i))=2{number of pairs (s,t):dist⁡(s,t)=2}n(n−1)≥2n(n−1)dmax⁡∑s,t∈V(G):dist⁡(s,t)=2σst=2n(n−1)dmax⁡∑i∈V(G)di(di−1)(1−ci)=2(n−1)dmax⁡(E(s)−E(sc))=2(1−C)E(s)(n−1)dmax⁡.\begin{aligned} L&=1+\frac{1}{n(n-1)}\sum_{i\in V(G)}BC(i)\ge1+\frac{1}{n(n-1)}\sum_{i\in V(G)}BC(i,\mathcal{N}^{1}(i))\\ &=\frac{2\{\text{number of pairs }(s,t):\operatorname{dist}(s,t)=2\}}{n(n-1)}\ge\frac{2}{n(n-1)d_{\max}}\sum_{\substack{s,t\in V(G):\\\operatorname{dist}(s,t)=2}}\sigma_{st}\\ &=\frac{2}{n(n-1)d_{\max}}\sum_{i\in V(G)}d_i(d_i-1)(1-c_i)=\frac{2}{(n-1)d_{\max}}\left(\mathbb{E}(s)-\mathbb{E}(sc)\right)=\frac{2(1-C)\mathbb{E}(s)}{(n-1)d_{\max}}. \end{aligned}

This theorem provides the additional relation to the relation in [6] between the average shortest path length and average clustering coefficient in graphs, but for any simple undirected graph:

Corollary 5. For any simple undirected graph

L≥1+(1−CWS)E(s)−cov⁡(s,c)(n−1)dmax⁡,L\ge1+\frac{(1-C_{WS})\mathbb{E}(s)-\operatorname{cov}(s,c)}{(n-1)d_{\max}},

where dmax⁡d_{\max} is the maximum degree.

Acknowledgments

Support from the Basic Research Program of the National Research University Higher School of Economics is gratefully acknowledged.

References

  1. [1]Shvydun S. ”Zoo of centralities: Encyclopedia of node metrics in complex networks.” arXiv preprint arXiv:2511.05122 (2025).arxiv.org/abs/2511.05122
  2. [2]Freeman, Linton C. ”A set of measures of centrality based on betweenness.” Sociometry (1977): 35-41.DOI
  3. [3]Freeman, Linton C. ”Centrality in social networks conceptual clarification.” Social networks 1.3 (1978): 215-239.DOI
  4. [4]Watts, Duncan J., and Steven H. Strogatz. ”Collective dynamics of ‘small-world’ networks.” nature 393.6684 (1998): 440-442.
  5. [5]Tuzhilin M. ”A series of real networks invariants.” arXiv preprint arXiv:2601.02052 (2026).arxiv.org/abs/2601.02052
  6. [6]Tuzhilin M. ”Relations between average shortest path length and another centralities in graphs.” Avtomatika i telemehanika 5 (2025): 114-122.DOI
  7. [7]Tuzhilin, M. ”Relations between average clustering coefficient and another centralities in graphs.” Moscow University Mathematics Bulletin 80.6 (2025): 335-341.DOI
  8. [8]Fosdick, Bailey K., et al. ”Configuring random graph models with fixed degree sequences.” Siam Review 60.2 (2018): 315-355.arxiv.org/abs/1608.00607
  9. [9]Škrekovski R., Gutman I. ”Vertex version of the Wiener theorem.” MATCH Commun. Math. Comput. Chem 72.1 (2014): 295-300.

Paper details

vlnc:W_pxrm5a92
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents