HomeResearchSocial NetworksEdge Balance Ratio —— Power Law from Vertices to Edges in Directed Complex Networks

Edge Balance Ratio —— Power Law from Vertices to Edges in Directed Complex Networks

1  Introduction

 

Edge balance ratio is a measure of the balance property of edges in directed networks. The concepts of edge balance ratio, balance profile and positivity are first proposed in the paper Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Networks, IEEE Journal of Selected Topics in Signal Processing, 7(2) 2013 by Xiaohan Wang, Zhaoqun Chen, Pengfei Liu and Yuantao Gu.

Edge balance ratio describes the balance level of edges in a directed network. For a directed edge from vertex A to B, edge balance ratio $R$ is defined as

$$R=\left\{ \begin{array}{ll} \displaystyle{\frac{d({\rm B})}{d({\rm A})}}, &d({\rm A})\neq0; \\ \infty, &d({\rm A})=0, \end{array} \right.$$

where $d({\rm B})$ and $d({\rm A})$ are the centralities of vertices B and A. The logarithmic edge balance ratio is defined as the logarithm of edge balance ratio, which is more convenient to describe the characteristics of the whole network.

For the whole network, balance profile is proposed as a global measure of the network, which is defined as the distribution of logarithmic edge balance ratio.

The positivity of a directed network can be defined as the expectation of logarithmic balance ratio with finite values. The expectation can be normalized by $\log{(N-1)}$,

$$p=\frac{1}{\log{(N-1)}}{\rm E}\{\log{R}\}=\frac{1}{|\mathcal E'|\log{(N-1)}}\sum_{({\rm A, B})\in {\mathcal E'}}\log{\frac{d_i({\rm B})}{d_i({\rm A})}},\nonumber$$

where $\mathcal E'$ is the set of edges with finite balance ratios. The range of positivity is $[-1, 1]$.

If the indegree distribution follows the power law, the distribution of edge balance ratio follows a piecewise power law, which is hat shaped. It means that edge balance ratio can build the power law relationship between vertices and edges.

 

2  Explanations

 

2.1  Edge Balance Ratio

 

The edge balance ratio reflects the balance property of edges. In a common network, the in-degree of a vertex roughly reflects its importance. An edge with a large edge balance ratio implies that the in-vertex has a much larger in-degree than the out-vertex, which implies that the in-vertex is very likely to be more important than the out-vertex. A balanced edge is one whose in-vertex and out-vertex have similar importance.

Unbalanced edges are common in real-world networks. Specially, in a directed network which follows power law, there are many edges pointing to the vertices with large in-degrees. Most of edges like these are unbalanced ones.

In microblogging networks there are abundant unbalanced edges. For instance, famous stars attract large amounts of followers. As a result, most of these edges are extremely unbalanced and edges like these account for a large proportion in microblogging networks. The edges with balance ratios far larger than one reflect the common following relationships, in which most users are likely to follow those more famous than themselves. Edges with balance ratios close to one represent the relationships between friends or people in similar social positions. Edges with balance ratios far less than one may contain much more information of the network, which means a highly ranked user follows an ordinary user, reflecting some hidden real-world relationships or inapparent information between individuals.

 

2.2  Balance Profile and Positivity

 

Since in-degree approximately reflects the importance of a vertex in the network, an edge with balance ratio larger than one can be called a positive edge. An edge pointing from a high in-degree vertex to a low in-degree vertex is a negative edge, correspondingly. An edge with balance ratio close to one can be called a normal edge. The balance profile reveals the overall trend of the edges in the network. It reflects much more information, including the proportion of unbalanced edges of various levels.

As the average of logarithmic balance ratios for edges, the positivity reveals the positive level of the whole network. Especially, for a directed network with all the edges bi-directed, it can be calculated that the positivity is zero. As an example, the in-degree distributions and balance profiles of four directed networks with different typical indegree distributions are illustrated in Fig.1. The four networks have different shapes of balance profiles. The positivities of the networks are 0.6474, 0.0437, 0.0019 and 0.0068, respectively. The power law network has a large positivity, because the positive half of the balance profile is significantly higher than the negative half. The balance profiles of the last two networks are almost symmetrical, which leads to rather small positivities.

 

 

Figure 1: The in-degree distributions and balance profiles of the four directed networks. The balance profiles have different shapes.

 

3  Mathematical Results

 

According to the properties of real-world directed networks, two basic assumptions are adopted in the network model.

   Assumption 1 The in-degrees of the vertices in the network follow power law distribution approximately,

$$N_k\approx A k^{-\gamma},$$

where $N_k$ is the amount of vertices with in-degree $k$, $A$ is a scale factor and $\gamma$ is the scaling exponent of power law. Assumption 1 is the power law assumption and Assumption 2 means that there is no bias on the followers of vertices on average.

   Assumption 2 For any vertex ${\rm V}_0$,

$$P(d_i({\rm V})=k | {\rm V}\in{\mathcal F}({\rm V}_0))\approx P(d_i({\rm V})=k),$$

where $P(d_i({\rm V})=k)$ is the probability that vertex ${\rm V}$ has in-degree $k$ and ${\mathcal F}({\rm V}_0)$ is the set of followers of vertex ${\rm V}_0$.

The main result on edge balance ratio is proposed as Theorem 1, which provides the approximate calculation of the edge balance ratio distribution.

   Theorem 1 If an $N$-vertex power law directed network satisfies Assumptions 1 and 2, for logarithmically divided counting intervals

$$[\cdots, \alpha^{-(s+1)}, \alpha^{-s}, \cdots,\alpha^{-2}, \alpha^{-1}, 1, \alpha, \alpha^2, \cdots, \alpha^s, \alpha^{s+1}, \cdots]$$

of edge balance ratio, the distribution of edge balance ratio follows power law piecewise. In detail, the amount of edges with balance ratio $R$ satisfies

$$N(R)\approx\displaystyle{\frac{{A}^2}{N}}\cdot\left\{ \begin{array}{ll}\displaystyle{\frac{1-\alpha^{1-\gamma}}{(\gamma-2)(2\gamma-3)}R^{\gamma-1}}, &R\ll1; \\ \displaystyle{\frac{1}{2\gamma-2}R^{\gamma}}, &R\lesssim1;\\ \displaystyle{\frac{1}{2\gamma-2}R^{1-\gamma}}, &R\gtrsim1; \\ \displaystyle{\frac{1-\alpha^{2-\gamma}}{(\gamma-2)(2\gamma-3)}R^{2-\gamma}}, &R\gg1. \end{array} \right.$$

The scaling exponents of the four sections are $\gamma-1$, $\gamma$, $1-\gamma$ and $2-\gamma$, respectively, where $\gamma$ is the scaling exponent of the in-degree distribution of the network.

 

4  Simulations and Statistics of Real Data

 

The statistical and theoretical balance profiles are indicated as the points and line segments in Fig. 2. With a smaller $\gamma$, one flatter hat is got and with a larger $\gamma$, a sharper hat is obtained. Especially for the case where $\gamma$ is equal to $1.9$, the theoretical analysis shows that the slope of this segment should be $-0.1$. The statistical balance profile rises when the balance ratio is larger, actually the same with the theoretical result.

 

 

Figure 2: The distributions of edge balance ratio for various scaling exponent $\gamma$.

 

The sub-figures at the top of Fig. 3 illustrate the in-degree distributions of the datasets of Twitter and Sina Weibo. Both the distributions show the same characteristics of power law. The scaling exponent of Twitter is larger than that of Sina Weibo.

The balance profiles of Twitter and Sina Weibo are illustrated in the sub-figures at the bottom of Fig. 3. Although the theoretical curves are similar with the statistics of real-world networks, they are not strictly the same. The in-degree distributions of real-world networks do not follow the power law strictly, and the following relationships are not strictly sampled uniformly. These reasons lead to the errors. Especially for the edge balance ratio of Twitter, there is a peak for large balance ratio, which can hardly be predicted. The reason for the peak is that users with lower ranks are more interested in following the users with very high ranks, which is not strictly the same with Assumption 2 in the following relationship.

 

 

Figure 3: The in-degree distributions and balance profiles of Twitter and Sina Weibo.

 

5  Download the paper

 

X. Wang, Z. Chen, P. Liu and Y. Gu, Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Networks, IEEE Journal of Selected Topics in Signal Processing, 7(2):184-194, 2013.

 

6  Contact the authors

 

For any question and comment about the website, please contact Yuantao Gu and Xiaohan Wang.