Extended Lorenz majorization and frequencies of distances in an undirected network

Let G=(V,E) be an undirected network, where V= (v_k)_k=1,…,N denotes the set of nodes or vertices and E denotes the set of links or edges. As collaboration (of scientists, universities, countries), bibliographic coupling (of articles, books), and co-citation (of articles, books) are all examples of undirected networks, it goes without saying that the study of these networks is of great importance for bibliometrics (Rousseau et al., 2018).

We assume that #V = N > 1. A chain in a network is a sequence of different nodes one by one connected by edges. The distance d between two nodes is equal to the number of links situated on a shortest chain (often called a shortest path) between these two nodes. Consequently, the distance between two nodes connected by an edge is equal to one. Each network studied in this article is assumed to be connected, i.e. there is a chain between any two nodes. Hence, for each node, there exists another node at a distance one. The total number of distances between any pair of nodes in this network is equal to N(N-1)/2, where, for v₁,v₂ ∈ V, d(v₁,v₂)=d(v₂,v₁) is considered only once.

Notation. We denote by α_j, j= 1,…, N-1, the number of times distance j occurs in network G. The array A=(α₁, α₂,…, α_N–1) is called the α-array or distance array of the network G.

Some immediate properties

1 ∑j=1N−1αj=N(N−1)2 \[\sum\limits_{j=1}^{N-1}{{{\alpha }_{j}}=\frac{N\left( N-1 \right)}{2}}\]

We give a short proof of

5 α2≤(N−1)(N−2)2 \[{{\alpha }_{2}}\le \frac{(N-1)(N-2)}{2}\]

Indeed, if α2>(N−1)(N−2)2\[{{\alpha }_{2}}>\frac{(N-1)(N-2)}{2}\] then N(N−1)2=∑j=1N−1αj≥α1+α2>(N−1)+(N−1)(N−2)2=N(N−1)2\[\frac{N(N-1)}{2}=\sum\limits_{j=1}^{N-1}{{{\alpha }_{j}}}\ge {{\alpha }_{1}}+{{\alpha }_{2}}>(N-1)+\frac{(N-1)(N-2)}{2}=\frac{N(N-1)}{2}\], which is a contradiction.

We recall the definition of the majorization order (Hardy et al., 1934). Let X = (x_j) and Y= (y_j), j=1,…, N-1 be two (N-1)-sequences of non-negative numbers, ordered decreasingly then X majorizes Y, denoted as X ⋟ Y, if 6 ∀i=1,…,N−2:∑j=1ixj≥∑j=1iyj \[\forall i=1,\ldots ,N-2:\sum\limits_{j=1}^{i}{{{x}_{j}}}\ge \sum\limits_{j=1}^{i}{{{y}_{j}}}\] and 7 ∑j=1N−1xj=∑j=1N−1yj \[\sum\limits_{j=1}^{N-1}{{{x}_{j}}}=\sum\limits_{j=1}^{N-1}{{{y}_{j}}}\]

We recall that if X ⋟ Y then the (standard) Lorenz curve of X (Lorenz, 1905) is situated above the Lorenz curve of Y. We now extend the notions of majorization and Lorenz curve by removing the requirement to be arranged in decreasing order.

Definition. Extended majorization order

Let X = (x_j) and Y=(y_j), j=1,…, N-1 be two (N-1)-sequences of non-negative numbers, then X majorizes Y (in the extended sense), denoted as X ⋟ Y (we keep the same notation), if 8 ∀i=1,…,N−2:∑j=1ixj≥∑j=1iyj \[\forall i=1,\ldots ,N-2:\sum\limits_{j=1}^{i}{{{x}_{j}}}\ge \sum\limits_{j=1}^{i}{{{y}_{j}}}\] and 9 ∑j=1N−1xj=∑j=1N−1yj \[\sum\limits_{j=1}^{N-1}{{{x}_{j}}}=\sum\limits_{j=1}^{N-1}{{{y}_{j}}}\]

Definition. Extended Lorenz curve

Let X = (x_j) be an (N-1)-sequence of non-negative numbers and let si=∑j=1ixj\[{{s}_{i}}=\sum\limits_{j=1}^{i}{{{x}_{j}}}\] be the j^th partial sum. Hence s_N-1 = TOT denotes the total sum of the numbers in X; s₀ is set equal to 0. Now plot the points (iN−1,siTOT)i=0,…,N−1\[{{\left( \frac{i}{N-1},\frac{{{s}_{i}}}{TOT} \right)}_{i=0,\ldots ,N-1}}\] and connect them by line segments to obtain a curve joining the origin (0,0) with the point (1,1). We refer to this curve as the extended Lorenz curve. Contrary to the standard Lorenz curve this curve is not necessarily concave (but of course still increasing). An example is shown in Figure 3. If X is decreasing then the extended Lorenz curve coincides with the classical Lorenz curve. If X ⋟ Y then the extended Lorenz curve of X is situated above the extended Lorenz curve of Y.

Given the number of nodes, N, we next show a majorization result between the frequency sequence of a complete network K_N, that of a general network G=(V, E), denoted as A, and the frequency sequence C of a chain.

Theorem

Given a network G=(V, E) with N nodes, then, (N(N−1)2,0,…,0)⋟A=(α1,α2,…,αN−1)⋟C=(N−1,N−2,…,1) \[\left( \frac{N(N-1)}{2},0,\ldots ,0 \right)\curlyeqsucc A=\left( {{\alpha }_{1}},{{\alpha }_{2}},\ldots ,{{\alpha }_{N-1}} \right)\curlyeqsucc C=(N-1,N-2,\ldots ,1)\]

By (8) and (9) the second inequality means that 10 ∀i=1,…,N−2:∑j=1iαj≥∑j=1i(N−j) \[\forall i=1,\ldots ,N-2:\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \sum\limits_{j=1}^{i}{(N-j)}\] and 11 ∑j=1N−1αj=∑j=1N−1(N−j) \[\sum\limits_{j=1}^{N-1}{{{\alpha }_{j}}}=\sum\limits_{j=1}^{N-1}{(N-j)}\]

We moreover prove that 12 αi≤∑j=iN−1αj≤(N−i+1)(N−i)2=:βi \[{{\alpha }_{i}}\le \sum\limits_{j=i}^{N-1}{{{\alpha }_{j}}}\le \frac{(N-i+1)(N-i)}{2}=:{{\beta }_{i}}\]

Proof. By (1), we already know that N(N−1)2=∑j=1N−1αj=∑j=1N−1(N−j) \[\frac{N(N-1)}{2}=\sum\limits_{j=1}^{N-1}{{{\alpha }_{j}}}=\sum\limits_{j=1}^{N-1}{(N-j)}\]

which proves (11). Assume now that α_i=0, for i > 1, then we already know that ∀k≥i:α_k=0 and thus ∑j=1iαj=∑j=1N−1αj=N(N−1)2≥∑j=1i(N−j) \[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}=\sum\limits_{j=1}^{N-1}{{{\alpha }_{j}}}=\frac{N(N-1)}{2}\ge \sum\limits_{j=1}^{i}{(N-j)}\]

Assume now that for some i > 1, α_i≠0, then we will prove that also in this case ∑j=1iαj≥∑j=1i(N−j)\[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \sum\limits_{j=1}^{i}{(N-j)}\]. This will be done in several steps. First, we show that ∑j=1iαj≥i(i+1)2\[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \frac{i(i+1)}{2}\]. Indeed: there exists in V at least one chain of length i, connecting nodes to which we refer as u₁, u₂, …, u_i+1. Then, by property 6, we know that ∀j=1,…, i: α_j≥i–j+1, and hence ∑j=1iαj≥(∑j=1i(i−j+1))=i(i+1)2\[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \left( \sum\limits_{j=1}^{i}{(i-j+1)} \right)=\frac{i(i+1)}{2}\]. In the next step, we show that this inequality can be refined to ∑j=1iαj≥(i(i+1)2)+i\[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \left( \frac{i(i+1)}{2} \right)+i\]. Indeed, as the network under study is connected, there exists a node in the network, denoted as u_i+2, connected to at least one node of the chain u₁, u₂, …, u_i+1. This point u_i+2 has a distance d, 0 < d ≤ i to at least i points in the chain. Now, adding the i distances involving the point u_i+2 we obtain ∑j=1iαj≥(i(i+1)2)+i\[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \left( \frac{i(i+1)}{2} \right)+i\]. We further note that ∀j ≤i, each point in the set S = {u₁, u₂, …, u_i+2} has at least j points in the set S at a distance 0 < d ≤ j.

Now we continue in this way. Assuming that we have a set T of i+n+1 connected nodes {u₁, …, u_i+1, u_i+2, …, u_i+n+1} from which we already derived that ∑j=1iαj≥(i(i+1)2)+(ni)\[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \left( \frac{i(i+1)}{2} \right)+(ni)\] and for which we know that ∀j ≤i each point in the set T, has at least j points in the set T at a distance 0 < d ≤ j. We again apply connectedness to get a new node u_i+n+2 at a distance d, 0 < d ≤ i to all points in T, leading to ∑j=1iαj≥(i(i+1)2)+(n+1)i\[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \left( \frac{i(i+1)}{2} \right)+(n+1)i\]. Again we observe that ∀j ≤i, each point in T* = {u₁, …, u_i+1, u_i+2, …, u_i+n+2} has a distance d, 0 < d ≤ j, with at least j points in the set T*. This procedure ends with n = N-i-2 for which ∑j=1iαj≥(i(i+1)2)+(N−i−1)i=Ni−∑j=1ij=∑j=1i(N−j)\[\sum\limits_{j=1}^{i}{{{\alpha }_{j}}}\ge \left( \frac{i(i+1)}{2} \right)+(N-i-1)i=Ni-\sum\limits_{j=1}^{i}{j}=\sum\limits_{j=1}^{i}{(N-j)}\] which proves the inequality in the case α_i≠0, and hence (10).

Now we prove (12). Using (10) and (11) we have: 12 ∀i=1,…,N−1:αi≤∑j=iN−1αj=∑j=1N−1αj−∑j=1i−1αj≤N(N−1)2−∑j=1i−1(N−j)=βi \[\forall i=1,\ldots ,N-1:{{\alpha }_{i}}\le \sum\limits_{j=i}^{N-1}{{{\alpha }_{j}}}=\sum\limits_{j=1}^{N-1}{{{\alpha }_{j}}}-\sum\limits_{j=1}^{i-1}{{{\alpha }_{j}}}\le \frac{N(N-1)}{2}-\sum\limits_{j=1}^{i-1}{(N-j)}={{\beta }_{i}}\]

where we still have to prove the final equality in (12). For this, we first observe that: βi−βi+1=(N−i+1)(N−i)2−(N−i)(N−i−1)2=(N−i) \[{{\beta }_{i}}-{{\beta }_{i+1}}=\frac{(N-i+1)(N-i)}{2}-\frac{(N-i)(N-i-1)}{2}=(N-i)\]

Now, N(N−1)2−∑j=1i−1(N−j)=N(N−1)2−∑j=1i−1(βj−βj+1)=N(N−1)2−(β1−βi)=βi \[\begin{matrix} \frac{N(N-1)}{2}-\sum\limits_{j=1}^{i-1}{(N-j)}=\frac{N(N-1)}{2}-\sum\limits_{j=1}^{i-1}{\left( {{\beta }_{j}}-{{\beta }_{j+1}} \right)} \\ =\frac{N(N-1)}{2}-\left( {{\beta }_{1}}-{{\beta }_{i}} \right)={{\beta }_{i}} \\ \end{matrix}\]

If N is fixed and the array A=(α₁, α₂,…,α_N–1) denotes the frequencies of the distances in a network, then 2N(N−1)∑i=1N−1iαi\[\frac{2}{N(N-1)}\sum\limits_{i=1}^{N-1}{i}{{\alpha }_{i}}\] denotes the average distance between nodes in this network, say d¯\[\bar{d}\].

Theorem. If A(1)=(α1(1),α2(1),…,αN−1(1))⋟A(2)=(α1(2),α2(2),…,αN−1(2))\[{{A}^{(1)}}=\left( \alpha _{1}^{(1)},\alpha _{2}^{(1)},\ldots ,\alpha _{N-1}^{(1)} \right)\curlyeqsucc {{A}^{(2)}}=\left( \alpha _{1}^{(2)},\alpha _{2}^{(2)},\ldots ,\alpha _{N-1}^{(2)} \right)\] then d1¯≤d2¯\[\overline{{{d}_{1}}}\le \overline{{{d}_{2}}}\].

Proof. As A(1)=(α1(1),α2(1),…,αN−1(1))⋟A(2)=(α1(2),α2(2),…,αN−1(2))\[{{A}^{(1)}}=\left( \alpha _{1}^{(1)},\alpha _{2}^{(1)},\ldots ,\alpha _{N-1}^{(1)} \right)\curlyeqsucc {{A}^{(2)}}=\left( \alpha _{1}^{(2)},\alpha _{2}^{(2)},\ldots ,\alpha _{N-1}^{(2)} \right)\], we know that ∀i=1,…,N−2:∑j=1iαj(1)≥∑j=1iαj(2)\[\forall i=1,\ldots ,N-2:\sum\limits_{j=1}^{i}{\alpha _{j}^{(1)}}\ge \sum\limits_{j=1}^{i}{\alpha _{j}^{(2)}}\] and ∑j=1N−1αj(1)=∑j=1N−1αj(2)\[\sum\limits_{j=1}^{N-1}{\alpha _{j}^{(1)}}=\sum\limits_{j=1}^{N-1}{\alpha _{j}^{(2)}}\]. Consequently: ∀i=2,…,N−2:∑j=iN−1αj(1)≤∑j=iN−1αj(2)\[\forall i=2,\ldots ,N-2:\sum\limits_{j=i}^{N-1}{\alpha _{j}^{(1)}}\le \sum\limits_{j=i}^{N-1}{\alpha _{j}^{(2)}}\].

Now, d¯1=2N(N−1)∑j=1N−1jαj(1)\[{{\bar{d}}_{1}}=\frac{2}{N(N-1)}\sum\limits_{j=1}^{N-1}{j}\alpha _{j}^{(1)}\] =2N(N−1)[ ∑j=1N−1αj(1)+∑j=2N−1αj(1)+…+∑j=N−1N−1αj(1) ]≤2N(N−1)[ ∑j=1N−1αj(2)+∑j=2N−1αj(2)+…+∑j=N−1N−1αj(2) ]=2N(N−1)∑j=1N−1jαj(2)=d2¯ \[\begin{array}{*{35}{l}} =\frac{2}{N(N-1)}\left[ \sum\limits_{j=1}^{N-1}{\alpha _{j}^{(1)}}+\sum\limits_{j=2}^{N-1}{\alpha _{j}^{(1)}}+\ldots +\sum\limits_{j=N-1}^{N-1}{\alpha _{j}^{(1)}} \right] \\ \le \frac{2}{N(N-1)}\left[ \sum\limits_{j=1}^{N-1}{\alpha _{j}^{(2)}}+\sum\limits_{j=2}^{N-1}{\alpha _{j}^{(2)}}+\ldots +\sum\limits_{j=N-1}^{N-1}{\alpha _{j}^{(2)}} \right] \\ =\frac{2}{N(N-1)}\sum\limits_{j=1}^{N-1}{j}\alpha _{j}^{(2)}=\overline{{{d}_{2}}} \\ \end{array}\]

Corollary. It follows from the previous theorem that the average distance between nodes in an N-node network is at most equal to the average distance in an N-node chain, namely (N+1)3\[\frac{(N+1)}{3}\] (see the appendix for the simple calculation of this value).

Remark. If G(A) denotes the Gini index of the array A of distance frequencies, we have 13 G(A)=1N−1(N−2d¯) \[G(A)=\frac{1}{N-1}(N-2\bar{d})\]

Hence, the Gini coefficient respects the extended majorization order. From (13) one can express d¯\[\bar{d}\] as a function of G(A): 14 d¯=N2−G(A)N−12 \[\bar{d}=\frac{N}{2}-G(A)\frac{N-1}{2}\]

The previous theorem shows that the operation of taking the average distance in an N-node network respects the opposite of the Lorenz majorization order, while the Gini coefficient respects this order.

Assume that we have an N-node chain, hence containing N-1 links. Then its set of distances contains (N−1)N2\[\frac{(N-1)N}{2}\] numbers and the median, Md, is either a natural number m or m-0.5. Then we have 1+2+…+(N−m)≥N(N−1)4>1+2+…+(N−m−1) \[1+2+\ldots +(N-m)\ge \frac{N(N-1)}{4}>1+2+\ldots +(N-m-1)\]

As for each natural number j, we have ∑k=1N−jk=(N−j)(N−j+1)2\[\sum\limits_{k=1}^{N-j}{k}=\frac{(N-j)(N-j+1)}{2}\], we can prove that m = [x] with (N−x)(N−x+1)2=N(N−1)4 \[\frac{(N-x)(N-x+1)}{2}=\frac{N(N-1)}{4}\]

from which it follows that x=(2N+1)−2N2−2N+12\[x=\frac{(2N+1)-\sqrt{2{{N}^{2}}-2N+1}}{2}\] and hence Md is either [x]-05 or [x]. For N large this leads to Md≈N(1−22)≈0.293N \[Md\approx N\left( 1-\frac{\sqrt{2}}{2} \right)\approx 0.293N\]

Consequently, limN→∞Mdd¯=3(1−22)≈0.879<1\[\underset{N\to \infty }{\mathop{\lim }}\,\frac{Md}{{\bar{d}}}=3\left( 1-\frac{\sqrt{2}}{2} \right)\approx 0.879<1\].

Moreover, we see that Md<d¯⇔N+12−22N2−N+12<N+13⇔N2−13N+4>0⇔N>12.7\[\operatorname{Md}<\bar{d}\Leftrightarrow N+\frac{1}{2}-\frac{\sqrt{2}}{2}\sqrt{{{N}^{2}}-N+\frac{1}{2}}<\frac{N+1}{3}\Leftrightarrow {{N}^{2}}-13N+4>0\Leftrightarrow \text{N}>12.7\]. Hence, in practice: N ≥ 13. Checking this manually for N = 2, …, 14 we find that also then Md<d¯\[\text{Md}<\bar{d}\] except for N = 2, 5, 8, and 11 in which cases Md=d¯\[\text{Md}=\bar{d}\].

The array of G₀ is (6,7,6,2,0,0). Figure 3 shows its extended Lorenz curve, situated between the extended Lorenz curve of K₇ (the complete network on 7 nodes) and the extended Lorenz curve of the chain of length 6. The average distances are respectively equal to 1, 2.19, and 2.67; the medians are 1, 2, and 2; while the corresponding Gini coefficients are: 0.833, 0.437, and 0.278.

Figure 3.

In this article, we introduced the study of the distance distribution of a network. We showed that the distance distribution in an undirected network majorizes the one of a chain and is always smaller (in the sense of majorization) than the distribution of the corresponding complete N-network. The Gini coefficient respects the majorization order for such distributions, while the average distance behaves oppositely. As a consequence, the average and median distances in any such network are smaller than those of a chain.

We intend to use these results in the study of small worlds and the so-called six degrees of separation property (work in preparation).