Relations between average shortest path length and another centralities in graphs

Mikhail Tuzhilin · 2024

Read Relations between average shortest path length and another centralities in graphs by Mikhail Tuzhilin (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03601.txt.

Introduction

Mikhail Tuzhilin relates graph distance averages to other network scores in a 2024 note. For simple graphs, he obtains formulas tying the average shortest path length to four standard measures: the average clustering coefficient, radiality, closeness, and stress centrality. Such ties mean one measure can be read from others, a shortcut when some are costly to compute on large networks.

Catalog record

CREATORMikhail Tuzhilin
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-03601

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Relations between average shortest path length and another centralities in graphs Mikhail Tuzhilin Abstract Relations between average shortest path length and radiality, closeness, stress centralities and average clustering coefficient were obtained for simple connected graphs. keywords Networks, centralities, local and global properties of graphs, average shortest path length, Watts-Strogatz clustering coefficient. 1 Introduction. Centrality measures are important characteristics in network science which contain intrinsic hidden information about networks. Centrality is a local (with relation to a vertex) or global (with relation to a whole graph) real functions on graphs. There exist many centralities [ 1 ] - [ 3 ] : local efficiency, radiality, closeness, betweenness, stress centralities, etc. One of the most important centralities for “real” networks (or small-world networks) are average clustering coefficient and average shortest path length [ 4 ] . The network is called small-world if it has small average shortest path length with relation to the size and big average clustering coefficient. This measures are separately calculated to prove that current network is small-world. In this article we proved that for geodetic graphs (or graphs with odd length cycles) with additional condition there is relation between average shortest path length and average clustering coefficient. 2 Main definitions. All subsequent definitions are given for a simple, connected, undirected graph G . Let’s denote by • V(G) the set of vertices, E(G) the set of edges and A=\{a_{ij}\} adjacency matrix of graph G . • Neighborhood N(v) — the induced subgraph in G on vertices which adjacent to the vertex v , • N^{\prime}(v) induced subgraph in G on vertices =V\big(N(v)\big)\bigcup\{v\} , • \bar{f}(x_{1},x_{2},...,x_{k}) , where f is any function V\times V\times...\times V\rightarrow\mathbb{R} , the restriction of this function on N^{\prime}(v) (for example \bar{L}(x,y) will be the average shortest path between x and y with restriction to subgraph N^{\prime}(v) ), • d_{i}=deg(v_{i}) , • n=|V(G)|,\;\;m=|E(G)| , • X(i)=X(v_{i}) for any X — set or function corresponding to vertex v_{i} , Let’s give definitions of centralities: 1. Diameter diam(G)=\max_{s,t\in V(G)}dist(s,t) . 2. Average shortest path length L(G)=\frac{1}{n(n-1)}\sum\limits_{s\neq t}dist(s,t) . 3. Local cluster coefficient c_{i}=c(i)=\frac{\text{number of edges in }N(i)}{\text{maximum possible number of edges in }N(i)}=\frac{2|E(N(i))|}{d_{i}(d_{i}-1)} . 4. Average clustering coefficient C_{WS}(G)=\frac{1}{n}\sum\limits_{i\in V(G)}c_{i}=\frac{1}{n}\sum\limits_{i\in V(G)}\frac{2|E(N(i)))|}{d_{i}(d_{i}-1)}=\frac{1}{n}\sum\limits_{i\in V(G)}\frac{\sum\limits_{j,k\in V(G)}a_{ij}a_{jk}a_{ki}}{d_{i}(d_{i}-1)} . 5. Global clustering coefficient C(G)=\frac{\text{number of closed triplets in $G$}}{\text{number of all triplets in $G$}}=\frac{\sum\limits_{i,j,k\in V(G)}a_{ij}a_{jk}a_{ki}}{\sum\limits_{i\in V(G)}d_{i}(d_{i}-1)} . 6. Closeness centrality Clo(v)=\frac{n-1}{\sum\limits_{t\in V(G)}dist(v,t)} . 7. Radiality Rad(v)=\frac{\sum\limits_{t\in V(G),t\neq v}(diam(G)+1-dist(v,t))}{n-1} . 8. Stress Str(i)=\sum\limits_{s,t\in V(G),\;s\neq t\neq i}\sigma_{st}(i) , where \sigma_{st}(i) is the total number of shortest paths from s to t which contains vertex i . Note that all centralities are non-negative and c_{i},C_{WS},\Clo(v) are less or equal 1. Also let’s give the definition of geodetic graph: Definition 1 . If there exists the unique shortest path between any two vertices in G then the graph G is called geodetic. This definition is equivalent to the condition then there is no even cycles in a graph. 3 Main results. Let’s consider a induced subgraph G^{\prime}\subset G . In general G^{\prime} can be not connected graph. In this case let’s define the average shortest path length for vertices of G^{\prime} with relation to the distance \dist in the ambient graph G . Let’s call L\big(N(i)\big) the local average shortest path length for the vertex i . Let’s start with simple relations: let’s proof the relation between local shortest path length and local clustering coefficient: Lemma 1 . L(N(i))=2-c_{i}. Proof. L(N(i))=\frac{1}{d_{i}(d_{i}-1)}\sum\limits_{s,t\in N(i),s\neq t}dist(s,t)=\frac{1}{d_{i}(d_{i}-1)}\sum\limits_{(s,t)\in E(N(i))}dist(s,t)+\sum\limits_{s,t\in N(i),(s,t)\notin E(N(i))}dist(s,t)= =\frac{1}{d_{i}(d_{i}-1)}(2|E(N(i))|+\sum\limits_{(s,i),(i,t)\in E(G),(s,t)\notin E(G)}dist(s,t))= =\frac{1}{d_{i}(d_{i}-1)}(2|E(N(i))|+2(d_{i}(d_{i}-1)-2|E(N(i))|))=2-c_{i}. Note that shortest paths for vertices in N(i) are defined corresponding to whole graph G . ∎ Averaging by i we obtain simple corollary about the relation between local shortest path length and average clustering coefficient. Corollary 1 . C_{WS}(G)=2-\frac{1}{n}\sum\limits_{i\in V(G)}L\big(N(i)\big). Let’s proof the relation between shortest path length in subgraph N^{\prime}(i) and shortest path length in N(i) . Lemma 2 . L\big(N^{\prime}(i)\big)=\frac{(d_{i}-1)L\big(N(i)\big)+2}{d_{i}+1}. Proof. By definition L\big(N^{\prime}(i)\big)=\frac{1}{(d_{i}+1)d_{i}}\sum\limits_{s,t\in V(N^{\prime}(i)),\;s\neq t}\dist(s,t)=\frac{d_{i}-1}{d_{i}+1}L\big(N(i)\big)+\frac{2}{d_{i}+1}. ∎ Let’s proof the relation between shortest path length in a induced subgraph and shortest path length in ambient graph if induced subgraph is obtained from ambient graph by deleting one vertex. Theorem 1 . Let a graph G is obtained from a connected simple graph G^{\prime} by deleting one vertex and |V(G)|=n . Then L(G^{\prime})\geq\frac{n}{n+1}L(G), where the average shortest path length L(G) is defined in the ambient graph G^{\prime} , if G is not connected. Proof. Let’s define the deleted vertex by v . By the triangle inequality \forall s,t\in V(G):\dist(s,v)+\dist(v,t)\geq\dist(s,t) , where the equality holds if, there are no paths from s to t in G . Therefore, \sum\limits_{s,t\in V(G),s\neq t}\big(\dist(s,v)+\dist(v,t)\big)\geq\sum\limits_{s,t\in V(G),s\neq t}\dist(s,t) \frac{2(n-1)}{n(n-1)}\sum\limits_{t\in V(G)}\dist(v,t)\geq\frac{1}{n(n-1)}\sum\limits_{s,t\in V(G),s\neq t}\dist(s,t) \frac{2}{n}\sum\limits_{t\in V(G)}\dist(v,t)\geq L(G) Then, L(G^{\prime})=\frac{1}{(n+1)n}\sum\limits_{s,t\in V(G^{\prime}),s\neq t}\dist(s,t)=\frac{1}{(n+1)n}\Big(2\sum\limits_{t\in V(G)}\dist(v,t)+\sum\limits_{s,t\in V(G),s\neq t}\dist(s,t)\Big)= =\frac{1}{n+1}\frac{2}{n}\sum\limits_{t\in V(G)}\dist(v,t)+\frac{n-1}{n+1}L(G)\geq\frac{n}{n+1}L(G) Note that if G consists of n isolated vertices then the equality holds. ∎ We obtain corollaries Corollary 2 . Let a graph G is obtained from a connected simple graph G^{\prime}\subset H by deleting one vertex, |V(G)|=n and H is connected and simple. Then L(G^{\prime})\geq\frac{n}{n+1}L(G), where the average shortest path lengths L(G) and L(G^{\prime}) are defined in the ambient graph H , if corresponded graphs are not connected. Proof. The proof is the same as for the previous theorem and also if G consists of n isolated vertices then the equality holds. ∎ Corollary 3 . L\big(N^{\prime}(i)\big)\geq\frac{d_{i}}{d_{i}+1}L\big(N(i)\big). Let’s proof the relation between shortest path length in a induced subgraph and shortest path length in ambient graph. Theorem 2 . Let’s G^{\prime}\subset G be induced subgraph and |V(G)|=n,|V(G^{\prime})|=n+k . Then L(G^{\prime})\geq\frac{n}{n+k}L(G), where the average shortest path length L(G) is defined in the ambient graph G^{\prime} , if G is not connected. Proof. Let’s construct the graph G^{\prime} from G by adding sequentially k vertices and corresponded edges. Let’s first sequentially add vertices adjacent to vertices of the graph G . Adding these vertices one by one we obtain a sequence of graphs G_{1},G_{2},...,G_{p}, where |V(G_{i})|=n+i . Further, let’s add is the same way vertices adjacent to vertices of the graph G_{p} and so on. In the end we obtain the graph G^{\prime} . By previous corollary \hskip-15.0ptL(G^{\prime})\geq\frac{n+k-1}{n+k}L(G_{k-1})\geq\frac{n+k-1}{n+k}\frac{n-k-2}{n-k-1}L(G_{k-2})=\frac{n-k-2}{n+k}L(G_{k-2})\geq\cdots\geq\frac{n}{n+k}L(G). ∎ Let’s proof the relation between average closeness centrality and average shortest path length: Lemma 3 . L(G)\geq\frac{n}{\sum\limits_{v\in V(G)}\Clo(v)}. Proof. By the inequality of harmonic mean and arithmetic mean \frac{1}{n}\sum\limits_{v\in V(G)}Clo(v)=\frac{1}{n}\sum\limits_{v\in V(G)}\frac{n-1}{\sum\limits_{t\in V(G)}dist(v,t)}\geq\frac{n(n-1)}{\sum\limits_{v,t\in V(G)}dist(v,t)}=\frac{1}{L(G)}. Note that an equality holds when all average shortest path lengths from any vertex to all remaining vertices are equal. ∎ Let’s proof the relation between average shortest path length and average radiality: Lemma 4 . L(G)=\diam(G)+1-\frac{1}{n}\sum\limits_{v\in V(G)}{\Rad}(v). Proof. The proof holds from definition \frac{1}{n}\sum\limits_{v\in V(G)}{Rad}(v)=\frac{1}{n}\sum\limits_{v\in V(G)}\frac{(n-1)(diam(G)+1)-\sum\limits_{t\in V(G),\;t\neq v}dist(v,t))}{n-1}=diam(G)+1-L(G). ∎ Now let’s prove theorem about a relation between average clustering coefficient and radiality using previous theorem. Theorem 3 . \frac{C_{WS}(G)}{2}\geq\frac{1}{n}\sum\limits_{i\in V(G)}\frac{\sum\limits_{v\in N(i)}\overline{\Rad}(v)}{d_{i}}-2+\frac{\#\{N(i)\text{ which are complete graphs}\}}{n}. Proof. By lemmas 3 : L(N^{\prime}(i))\geq\frac{d_{i}}{d_{i}+1}L(N(i))\geq\frac{1}{2}L(N(i))=1-\frac{1}{2}c_{i} . Therefore, \frac{1}{d_{i}}\sum\limits_{v\in N(i)}\overline{\Rad}(v)=\diam(N^{\prime}(i))+1-L(N^{\prime}(i))\leq\diam(N^{\prime}(i))+\frac{1}{2}c_{i}=\frac{1}{2}c_{i}+2-\chi_{K_{d_{i}}}(N(i)), where \chi_{K_{d_{i}}}(N(i))=\begin{cases}1&\text{if $N(i)=K_{d_{i}}$}\\ 0&\text{otherwise}\end{cases} . Averaging by i ends the proof. ∎ Let’s prove a theorem about a connection between the average stress centrality and average shortest path length for geodetic graphs. Theorem 4 . If G is geodetic, then L(G)=1+\frac{1}{n(n-1)}\sum\limits_{i\in V(G)}\Str(i). Proof. Let’s define \chi_{st}(i)=\begin{cases}1&\text{if $i\neq s\neq t$ is the vertex of the shortest path between $s$ and $t$,}\\ 0&\text{otherwise.}\end{cases} Thus, \Str(i)=\sum\limits_{s,t\in V(G)}\chi_{st}(i) . If there exists the unique shortest path between any two vertices in G ,

Read the complete text