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 j-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 j-neighborhood centralities. In this context, Laplacian-based j-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 j-neighborhood centralities (including degree and ksi-centralities).
J-neighborhood centrality and its properties
Here we propose new relations of j-neighborhood centrality from [5]. This centrality is a set of centralities ξij for a vertex i parametrized by j:
ξij=(χij,χij)(Lχij,χij)
where χij(k) is the characteristic function of Nj(i), that is
χij(k)={1,0,k∈Nj(i),otherwise.
For j=0 and 1 this centrality coincides with degree and ksi-centrality respectively. For larger j 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 j-neighborhood Nj(i) of a vertex i and of the set of edges E(A,B) from the set A to B from [5].
Lemma 1. Let’s fix some vertex i. For j-neighborhood centrality holds
ξij=∣Nj(i)∣{number of shortest paths from i to all vertices of length j}+{the same of length j+1}
The first holds the fact, that there is a bijection between the number of shortest paths from i to all vertices of length j and edges of E(Nj−1(i),Nj(i)).
The second holds from two facts: the maximum number of edges E(Nj−1(i),Nj(i)) is ∣Nj−1(i)∣⋅∣Nj(i)∣ and for any vertex of Nj(i) there exists a least one adjacent edge from E(Nj−1(i),Nj(i)). Therefore, holds
∣Nj(i)∣≤E(Nj−1(i),Nj(i))≤∣Nj−1(i)∣⋅∣Nj(i)∣.
The same for E(Nj(i),Nj+1(i)).
This lemma allows us to define normalized versions of j-neighborhood centralities in two different ways:
where C2j+1(G) is the number of 2j+1-cycles in the graph.
Proof. Let’s note that
ξij∣Nj(i)∣=i∈Nj(i)∑di−2∣E(Nj(i))∣.
For a fixed i each edge E(Nj(i)) corresponds to different 2j+1-cycle in G. Therefore, C2j+1(G)≥(2j+1)∑i∈V(G)E(Nj(i)).
Lemma 4.For any simple graph
i∈V(G)∑j=0∑Dξij∣Nj(i)∣=2i∈V(G)∑Str(i),
where ∣Nj(i)∣=0, if there is no vertices k:dist(i,k)=j.
Proof. By the lemma 1:
j=0∑Dξij∣Nj(i)∣=2{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 G:
degree di, i∈V(G),
let’s denote si=di(di−1), i∈V(G),
local cluster coefficient ci=maximum possible number of edges in N1(i)number of edges in N1(i)=di(di−1)2∣E(N1(i))∣,
average clustering coefficient CWS=n1∑i∈V(G)ci=n1∑i∈V(G)di(di−1)∑j,k∈V(G)aijajkaki,
global clustering coefficient C=number of all triplets in Gnumber of closed triplets in G=∑i∈V(G)di(di−1)∑i,j,k∈V(G)aijajkaki,
vertex eccentricity e(i)=maxt∈V(G)d(i,t),
diameter D=maxs,t∈V(G)dist(s,t),
average shortest path length L=n(n−1)1∑s,t∈V(G):s=tdist(s,t),
stress Str(i)=∑s,t∈V(G):s=t=iσst(i), where σst(i) is the total number of shortest paths from s to t which contains vertex i,
betweenness BC(i)=∑s,t∈V(G):s=t=iσstσst(i), where σst is the total number of shortest paths from s to t.
Theorem 1.For average and global clustering in simple undirected graph hold
C−CWS=E(s)cov(s,c),
where expected value E(s)=n1∑i∈V(G)si and covariance cov(s,c)=E((s−E(s))(c−E(c))).
Proof. Note that ∑j,k∈V(G)aijajkaki=sici, thus C=E(sc)/E(s). Therefore,
E(s)cov(s,c)=E(s)E(sc)−E(c)=C−CWS.
From this theorem we obtain
Corollary 1. For any simple undirected graph
if cov(s,c)>0, then C>CWS,
if cov(s,c)<0, then C<CWS.
This corollary generalizes the result in [6], since if both s and c are monotonically increasing, covariance cov(s,c)>0 and vice versa: if both s and c are monotonically decreasing, covariance cov(s,c)<0.
Corollary 2. For any simple undirected graph
∣C−CWS∣≤E(s)var(s)var(c).
This corollary shows that the standard deviations of s 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=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 G
i∈V(G)∑ξidi=i∈V(G)∑di2−6T(G),
where T(G) is the number of triangles or closed triplets in G.
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 j-neighborhood centrality.
Corollary 4. For any simple undirected graph we have a sequence of inequalities
In particular, we obtain a boundaries for closeness centrality in terms of diameter, ksi and degree for graphs with D≥2:
D(n−1)−(D−1)di−(D−2)ξin−1≤Clo(i)≤ξ−1n−1.
The next two theorems gives new upper and lower bounds on the average shortest path length in terms of averages of j-neighborhood centralities and global clustering coefficients.
Theorem 2.For any simple undirected graph G with D≥4 we have a sequence of inequalities
where d is the average degree, d2 — mean square degree, Ξj — average j-neighborhood coefficient and T(G) — the number of triangles in the graph. For smaller diameters D(G)=1,2,3 truncated sequences can be used.
By this theorem we obtain bounds for the average shortest path length for the graphs with D≥2 in terms of diameter, average degree and average ksi-coefficient:
n−1Ξ−1≤L(G)≤D−n−1(D−1)d+(D−2)(Ξ−1).
Theorem 3.For any simple undirected graph
L≥1+(n−1)dmax(1−C)E(s),
where dmax 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σst(i), where shortest paths between vertices s,t are calculated in the whole graph G.
For average local betweenness holds
i∈V(G)∑BC(i,N1(i))=i∈V(G)∑s,t∈N1(i):(s,t)∈/E(N1(i))∑σst1=2{number of pairs (s,t):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≤dmax{number of pairs (s,t):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+n(n−1)1i∈V(G)∑BC(i)≥1+n(n−1)1i∈V(G)∑BC(i,N1(i))=n(n−1)2{number of pairs (s,t):dist(s,t)=2}≥n(n−1)dmax2s,t∈V(G):dist(s,t)=2∑σst=n(n−1)dmax2i∈V(G)∑di(di−1)(1−ci)=(n−1)dmax2(E(s)−E(sc))=(n−1)dmax2(1−C)E(s).
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+(n−1)dmax(1−CWS)E(s)−cov(s,c),
where dmax 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]Shvydun S. ”Zoo of centralities: Encyclopedia of node metrics in complex networks.” arXiv preprint arXiv:2511.05122 (2025).arxiv.org/abs/2511.05122
[2]Freeman, Linton C. ”A set of measures of centrality based on betweenness.” Sociometry (1977): 35-41.DOI
[3]Freeman, Linton C. ”Centrality in social networks conceptual clarification.” Social networks 1.3 (1978): 215-239.DOI
[4]Watts, Duncan J., and Steven H. Strogatz. ”Collective dynamics of ‘small-world’ networks.” nature 393.6684 (1998): 440-442.
[5]Tuzhilin M. ”A series of real networks invariants.” arXiv preprint arXiv:2601.02052 (2026).arxiv.org/abs/2601.02052
[6]Tuzhilin M. ”Relations between average shortest path length and another centralities in graphs.” Avtomatika i telemehanika 5 (2025): 114-122.DOI
[7]Tuzhilin, M. ”Relations between average clustering coefficient and another centralities in graphs.” Moscow University Mathematics Bulletin 80.6 (2025): 335-341.DOI
[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]Škrekovski R., Gutman I. ”Vertex version of the Wiener theorem.” MATCH Commun. Math. Comput. Chem 72.1 (2014): 295-300.