In this paper, we introduce two novel evolutionary processes for hierarchical networks referred to as dominance- and prestige-based evolution models, i.e., DBEM and PBEM, respectively. Our models are deterministic in nature which allows for closed-form derivation of equilibrium points for such type of networks, for the special case of complete networks. After deriving these equilibrium points, we are somewhat surprised in recovering the exponential and power-law strength distribution as the shared property of the resulting hierarchal networks. Additionally, we compute the network properties, Geodesic distance distribution and centrality closeness, for each model in closed form. Interestingly, these results demonstrate very different roles of hubs for each model, shedding the light on the evolutionary advantages of hierarchies in social networks: in short, hierarchies can lead to efficient sharing of resources and robustness to random failures. For the general case of any hierarchical network, we compare the estimations of tie intensities and node strengths using the proposed models to open-source real-world data. The prediction results are statistically compared using the Kolmogorov–Smirnov test with the original data.
1 Introduction
To analyze the emergence of social networks, a variety of mathematical models have been proposed. The earliest dates back to the 1900s, where Yule (1925) studied the biological evolution of species based on age and population data. Others, e.g., Lotka (1926) provided rules required for describing and analyzing scientific publications. Resulting from these studies, was the identification of the power-law degree distribution Cancho and Fernández (2008) as a shared common characteristic for a wide range of networks including the world wide web, protein–protein interaction, airlines, and social networks.
Given such a widely-shared characteristic, Barabási and Albert suggested a preferential attachment model for the generation of scale-free graphs exhibiting a power-law degree distribution Barabási and Albert (1999). As noted by Durrett (2006), the definition of their process was rather informal. Since then, different precise forms of the Barabási-Albert model have been studied in the literature Bollobás and Riordan (2003). Though successful at recovering the power-law degree distribution, these studies impose several restricting assumptions on the underlying graph generating process. For instance, such techniques typically adopt a binary attachment model, in which two nodes are either connected or not Barabási and Albert (1999), Watts and Strogatz (1998). Apart from this modeling restriction, another problem inherent to existing binary models lies in their explanatory capabilities. For instance, they fail to manifest connection strengths between individuals, a property being at the core of behavioral emergence in real networks Barrat et al. (2004), Granovetter (1973), Newman (2001), Barrat et al. (2004), Garlaschelli et al. (2005), Ranjbar-Sahraei et al. (2014).
Anzeige
On the other hand, the existence of hierarchical relationships is another shared common characteristic for a wide range of networks Clauset et al. (2008), Mones et al. (2012). Research has shown that human physique and body hormones play a crucial role in enabling dominance in the society. While most of the animal societies base their hierarchies on dominance, human societies replace dominance by “prestige” to construct reciprocal relationships between leaders and followers Price and Van Vugt (2014). Thus, evolutionary considerations of real-world networks suggest the emergence of scale-free behavior (i.e., networks exhibiting a power-law degree distribution) in networks as a result of hierarchal attachment processes that are not reflected through current preferential attachment models.
To provide more realistic modeling outcomes, in this paper, we contribute by proposing deterministic hierarchal evolution processes for dominance-based and prestige-based societies. Contrary to preferential attachment models, our approach only assumes hierarchal connections between individuals, thus bridging the modeling gap to real-world evolutionary networks. Among many advantages, our deterministic setting enables the derivation of the strength distribution in closed form. Performing this derivation recovers, surprisingly, the exponential and power-law degree distribution as the main property of the resultant hierarchal networks, which explains the prevalence of such hierarchies in societies.
In short, our contributions can be summarized as (a) providing a deterministic modeling of linear hierarchal networks.1 (b) validating the proposed model by four real-world datasets, and (c) measuring the time complexity and assortativity of the proposed models. Moreover, for the specific case of hierarchical networks with all-to-all connections among individuals we (d) derive, for the first time, a closed form of the skewed distribution among individuals in networks having hierarchical interactions; (e) explain the prevalence of hierarchies in societies as a resultant of the characteristics of derived skewed distribution (e.g., high robustness and small average distance Albert and Barabási 2002), and (f) compute the Geodesic distance and closeness centrality of the networks in closed form.
The remainder of this paper is organized as follows. The notations and preliminary information on mathematical series and degree distributions are provided in Sect. 2. The dominance-based and prestige-based evolution models are introduced in Sect. 3. Each of these models are studied in detail in Sects. 4 and 5, and their network properties are further studied in Sect. 6. Section 7 provides real-world verification of the proposed models, and Sect. 8 discusses the results. Section 9 concludes.
Anzeige
2 Preliminaries
In this section, we present the basic notations and definitions that will be used throughout this paper.
2.1 Notation
2.1.1 General notation
We define a network as a weighted graph, \({\mathbb {G}} = \left( {\mathbb {V}},{\mathbb {W}}\right)\), consisting of a set of N nodes (or vertices) \({\mathbb {V}} = \{{\varvec{v}}_1, \ldots ,{\varvec{v}}_{N}\}\) and an \(N \times N\) adjacency matrix \({\mathbb {A}}\) as:
Note that we handle the symmetric setting, where if node \({\varvec{v}}_{i}\) exhibits a tie with \({\varvec{v}}_{j}\), then \([{\mathbb {A}}]_{ij}={\varvec{a}}_{ij}={\varvec{a}}_{ji}=1\). \(N \times N\) weight matrix \({\mathbb {W}}\) is used to depict the strength of a tie between two vertices \({\varvec{v}}_{i}\) and \({\varvec{v}}_{j}\), i.e., if \({\varvec{a}}_{ij}=1\), \([{\mathbb {W}}]_{ij}={{\varvec{w}}}_{ij}={{\varvec{w}}}_{ji} \ne 0\) else \({{\varvec{w}}}_{ij}={{\varvec{w}}}_{ji}=0\).
Finally, the neighborhood of a node \({\varvec{v}}_i\), \({\mathbb {N}}({\varvec{v}}_{i})\), is defined as the set containing its adjacent vertices, i.e., \({\mathbb {N}}({\varvec{v}}_i) = \{v_j\mid a_{ij}=1\}\). Consequently, the degree of a node \({\varvec{v}}_{i}\), \(\text {deg}({\varvec{v}}_i)\), is given by the cardinality of \({\mathbb {N}}({\varvec{v}}_{i})\).
2.1.2 Network hierarchy notation
Consider a hierarchical constitution for \({\mathbb {G}}\) such that each individual i observes the tie strengths between every two individuals j and k if \(k<i\), \(j<i\) and \({\varvec{a}}_{kj} = 1\). An individual j is called superior to i if \(j<i\) and \({\varvec{a}}_{ij} = 1\). Therefore, we define \({\mathbb {H}}\) as the set of all tuples (j, i) such that j is superior to i.
The strength of a node is of major importance in the analysis of hierarchical networks. Next, we define three concepts needed in the remainder of the paper being relative strength, strength observation, and absolute strength.
The relative node strength is defined relative to two nodes i and j. Thus, the relative strength of \(j{\hbox {th}}\) node with respect to \(i{\hbox {th}}\) node with \(j<i\), denoted by \(\varvec{\varPsi }_{i}({\varvec{v}}_{j})\), represents the sum over all edge weights between \(j{\hbox {th}}\) node and every kth node with \(k<i\):
In words, when node i is observing node j with \(j<i\), it just observes these connections from the other nodes k to j which satisfy \(k<i\). The importance of this concept will be shown in Sect. 4.
The strength observation of \(i{\hbox {th}}\) node is denoted by the vector
This vector contains the observations of \(i{\hbox {th}}\) node from every other superior \(j{\hbox {th}}\) node (i.e., \((i,j)\in {\mathbb {H}}\)). As we will show in next section, the strength of each tie that \(i{\hbox {th}}\) individual establishes with superiors depends on the values of such an observation vector. Finally, the absolute strength (i.e., the strength recorded by an external observer) of node i is defined as:
The harmonic series and fraction product are two ingredients which are needed in our analysis for determining closed forms of the strength distributions. Here, we provide two lemmas presenting upper and lower bounds on the values of such summations.
The relatively simple proof of the above lemma is based on the integration results of harmonic series, where \(L_H(i,N)\) is lower bounded by \(\int _{x=i-1}^{N} \frac{1}{x} \mathrm {d}x\) and upper bounded by \(\int _{x=i}^{N+1} \frac{1}{x}\mathrm {d}x\). \(\square\)
Lemma 2
(Fraction Product Series) Consider the following product of fractions
Clearly, \(L_F(i,N)<Q(i,N)\) and \(L_F(i,N)Q(i,N)= \frac{2N-2}{2i-2}\). Therefore, \(L_F(i,N)<\sqrt{ \frac{2N-2}{2i-2}} \le \gamma (i-1)^{-\frac{1}{2}}\) concluding the upper-bound. To determine the lower bound, define
2.3 Power-law and exponential degree distributions
In the analysis of weighted networks, typically the Distribution Function (DF) is introduced:
$$\begin{aligned} P(k) = \bigg |\bigg \{{\varvec{v}}_i | \forall i, k \le \varvec{\varPsi }_{}({\varvec{v}}_{i}) < k+1 \bigg \}\bigg |, \end{aligned}$$
(6)
where \(\varvec{\varPsi }_{}({\varvec{v}}_{i})\) defined in (2) denotes the strength of node \({\varvec{v}}_i\) and \(|\cdot |\) being the cardinality of the corresponding set. To ease the analysis, in this work, we make use of the Complementary Cumulative Distribution Function (CCDF) defined as:
The following two lemmas signify the relation between DFs and CCDFs for networks with power-law and exponential distributions:
Lemma 3
(Exponential Distribution) Consider an exponential distribution of the form\(P(k) = c e^{-\alpha k}\). The CCDF can be written as\(P_c(k) = \frac{c}{\alpha } e^{-\alpha k}\).
Proof
Can be easily seen by simple integration.\(\square\)
Lemma 4
(Power-law Distribution) Consider a power-law distribution in form of\(P(k) = c {k} ^{-\alpha }\), where\(\alpha\) is the power-law exponent. The CCDF\(P_c(k)\) also follows a power-law but with an exponent\(\alpha -1\).
Proof
Can be easily seen by simple integration. \(\square\)
Having laid out our notation and providing the required background knowledge, next, we present and analyze two dynamical models that reflect networks constructed by dominance- and prestige-based evolutionary models. Not only we provide iterative constructing algorithms, but also present a set of theorems studying their stationary points, which interestingly relate to the exponential and power-law distributions.
3 Network dynamics in hierarchical networks
We propose, for the first time, a dynamical process which captures the edge dynamics of hierarchical networks. Let \({{\varvec{w}}} = \{w_{ij}|\forall (i,j)\in {\mathbb {H}} \}\) denote the state vector of the process. Each state variable \(w_{ij}\) corresponds to the weight of the link between \(j{\hbox {th}}\) and \(i{\hbox {th}}\) node. To determine the dynamics of the change in the state variable, one typically considers the rate of change in \(w_{ij}\) as a function of all state variables:
In other words, we assume that the dynamics of the linking strength between i and j are independent of any other node l which is higher than i or j in the hierarchy.
Using \(f_{\varPsi }\) from Eq. 9, sorting the state variables \(w_{ij}\) increasingly (based on \(Ni+j\)), the overall dynamic process can be written as
To finalize the dynamical model, \(f_{{\varPsi }}(\cdot )\) has to be defined. Considering real-world hierarchal networks, next, we introduce two such models, \(f_{{\varPsi }}^{(\mathbb {D})}(\cdot )\) and \(f_{{\varPsi }}^{(\mathbb {P})}(\cdot )\) corresponding to dominance and prestige-based dynamics.
4 Dominance-based evolution model (DBEM)
In the dominance-based evolution model (DBEM), the strength of ties between \(i{\hbox {th}}\) and every other \(j{\hbox {th}}\) individual, with \((i,j) \in {\mathbb {H}}\) and \(i>1\), follows a simple dynamical rule:
In the above, \(\big |\varvec{{\varPsi }}_{i}\big |\) is a fixed integer denoting the number of superiors to \(i{\hbox {th}}\) individual. The difference between \(\frac{1}{\big |\varvec{{\varPsi }}_{i}\big |}\) and \(w_{ij}\) determines the direction of changes of \(w_{ij}\) (i.e., \(\dot{w}_{ij}\)).
For computing the equilibrium point of the above system, consider an energy function for \(w_{ij}\) of the form:
Using the invariant set theorem Slotine and Li (1991), we can show that the overall dynamical process has a stable equilibrium point, in which the link between \(i{\hbox {th}}\) and \(j{\hbox {th}}\) node, \(j<i\), converges to \(w_{i\star }^{(\mathbb {D})}\):
The equilibrium point in (14) explains that the links of node i to all nodes with lower order (i.e., \(j<i\)) depend on i. Further, it clarifies that the higher the order is the lower the strength of links are.
Example To illustrate, consider N agents in a complete graph. Continuously each agent shares its available resources to superior agents. The strength of the connection between nodes i and j reflects the amount of resources transmitted from i to j. According to (14), the second individual shares all resources with \(1{\hbox {st}}\) (i.e., \(w_{21} = \frac{1}{2-1} = 1\)). The third, however, shares half of the resources with the second, and the other half with the first (i.e., \(w_{32} = w_{31} = \frac{1}{3-1} = \frac{1}{2}\)). Similarly, any agent i shares \(\frac{1}{i-1}\) units of the resources with each of the j individuals as long as \(j<i\). Therefore, one can see that this model directly captures the dominance of individuals in a linear hierarchical network, where every individual is sharing resources among dominated individuals.
Next, we study the amount of resources each individual receives in such dominance-based network (captured by node’s strengths) and compute the distribution of node strengths.
In the following subsections, we focus on complete networks (allowing us to derive numerous characteristics in closed form) where every \(j{\hbox {th}}\) individual is superior to \(i{\hbox {th}}\) individual if \(j<i\). Thus, \(\big |\varvec{{\varPsi }}_{i}\big | = i-1\)\(\forall i>1\), and
Building on \({w}^{(\mathbb {D})}_{i\star }\)’s definition in Eq. 15, one can calculate the absolute strength of \(i{\hbox {th}}\) node, \(\varvec{\varPsi }_{}({\varvec{v}}_{i})\) as:
The distribution of strengths in the DBEM model can be directly computed from the bounds provided in Eq. 17. The following theorem shows how the CCDF, and consequently the DF of strengths in this model follow an exponential distribution:
Theorem 1
(Strength Distribution in DBEM Model) For the complete weighted network\({{\mathbb {G}}}\), generated using the DBEM model, the DF of the global strengthkfollows an exponential distribution of the form
Using Lemma 3, it is straightforward to see that the DF corresponding to (19) is exponential, i.e., \(P(k) \propto e^{-k}.\)\(\square\)
5 Prestige-based evolution model (PBEM)
Having introduced the above model, next, we present a prestige-based model, taking our framework a step closer to the formation of hierarchies in real social networks. Consider an arbitrary undirected network with \({\mathbb {A}}\) as its adjacency matrix and \({\mathbb {H}}\) as its hierarchical structure. The overall strength of node i in establishing connections with every other \(j{\hbox {th}}\) node with \((i,j) \in {\mathbb {H}}\) and \(i>1\) is assumed to be limited and sums to 1. Let
By studying the dynamic process proposed in Eq. 21, it can be easily seen that \(\dot{w}_{ij}, \ i>j\) is a function of \(w_{kl}\) for all \(k,l < i\). Without loss of generality, we assume \({{\varvec{w}}}^{(\mathbb {P})}_{11} =1\), such that:
We also assume that \({{\varvec{w}}}^{(\mathbb {P})}_{ii} = 0\) for every \(i>1\). It is again straightforward to compute the equilibrium point of such system as:
It is clear that the equilibrium point in (23) explains that the connection strength between node i and node j depends on the strength of the ties between nodes i or j and every other kth node with \(k< \max \{i,j\}\).
Example To illustrate, imagine N agents in a complete graph. Continuously the agents with higher-order share their available resources with agents exhibiting lower order. The strength of the link between i and j shows the amount of resources which are transmitted. According to (23), the second agent shares all resources with the first individual (i.e., \(w_{21} = \frac{1}{1} = 1\)). The third agent shares one-third of the resources with the second and two-thirds with the first (i.e., \(w_{32} = \frac{1}{1 + 2} = \frac{1}{3}\) and \(w_{31} = \frac{2}{1 + 2} = \frac{2}{3}\)). Similarly, the ith agent shares portions of the resources with each of the j agents with \(j<i\). Those with a lower order, however, receive higher resources compared to the ones with a higher order. This also explains our naming referring to the model as a prestige-based one, where lower orders reflect a “prestige” in the group receiving more resources compared to others.
Next, we focus on complete networks where every \(j{\hbox {th}}\) individual is superior to \(i{\hbox {th}}\) individual if \(j<i\). For such networks, we will compute the amount of resources each individual receives and also the distribution of node strengths.
5.1 Analysis of node’s strength
Given a complete network, here, we determine a closed-form solution for the sum over the strength of every \(j{\hbox {th}}\) node from the perspective of \(i{\hbox {th}}\) node, as long as \(j<i\).
Lemma 5
In the prestige-based evolution model, the sum of the relative node strengths of every\(j{\hbox {th}}\)node from perspective of\(i{\hbox {th}}\)node, with\(j<i\)is:
Initial Step: According to Eq. (22), we have \(|\varvec{{\varPsi }}_{2}| = \varvec{\varPsi }_{2}({\varvec{v}}_{1}) = 1\). Therefore, \({\varvec{K}}(i)\) holds for \(i=2\).
and also note that \(\varvec{\varPsi }_{i}({\varvec{v}}_{j}) = \varvec{\varPsi }_{i-1}({\varvec{v}}_{j}) + {{\varvec{w}}}^{(\mathbb {P})}_{(i-1)j}\). Therefore we can write:
holds for every \(j < i-1\). For computing the edge weight between \(i{\hbox {th}}\)and \(j{\hbox {th}}\) node, recall that \(\varvec{\varPsi }_{i}({\varvec{v}}_{j}) = \varvec{\varPsi }_{i-1}({\varvec{v}}_{j}) + {{\varvec{w}}}^{(\mathbb {P})}_{(i-1)j}\). By using (23) and Lemma 5, it can be seen that:
for \(j < i-1\). Therefore, \({\varvec{K}}(i)\) holds for every i, concluding the proof. \(\square\)
Before, computing the distribution of strengths for PBEM, we present the following proposition providing the relative strength of \(j{\hbox {th}}\) node from the perspective of \(i{\hbox {th}}\) for every \(i>j\) in closed form:
Proposition 1
(Relative Node Strength) For the weighted graph\({{\mathbb {G}}}\), evolved according to PBEM, the strength of the\(j{\hbox {th}}\)node from perspective of the\(i{\hbox {th}}\)node is given by:
Again, induction can be used to prove the validity of Eq. 28. Starting with the initial step we get:
Initial Step: From Eq. 22, the strength of the first node from the perspective of the second node is \(\varvec{\varPsi }_{2}({\varvec{v}}_{1}) =1\). Besides, using Lemma 6, we can deduce that:
For computing \(\varvec{\varPsi }_{i}({\varvec{v}}_{j})\), consider \(\varvec{\varPsi }_{i}({\varvec{v}}_{j}) = \varvec{\varPsi }_{i-1}({\varvec{v}}_{j}) + {{\varvec{w}}}^{(\mathbb {P})}_{(i-1)j}\). Using Eq. 23 and Lemma 5, we can show that for every \(j < i-1\):
Besides using Eq. (24), \(\varvec{\varPsi }_{i}({\varvec{v}}_{j})\) = 1 for \(j = i-1\). Therefore, \({\varvec{K}}(i)\) holds for every i and the proof is concluded. \(\square\)
Lemma 7
(Global Strength) For the weighted graph\({{\mathbb {G}}}\), evolved with PBEM, the global strength of the\(i{\hbox {th}}\)node is:
$$\begin{aligned} \left\{ \begin{array}{ll} \varvec{\varPsi }_{}({\varvec{v}}_{i}) = \prod _{k=i+2}^{N+1}\frac{2k-4}{2k-5} &{} \quad \hbox {for}\; i < N \\ \varvec{\varPsi }_{}({\varvec{v}}_{i}) = 1 &{} \quad \hbox {for}\; i = N. \end{array} \right. \end{aligned}$$
(29)
Proof
We know that \(\varvec{\varPsi }_{}({\varvec{v}}_{i}) = \varvec{\varPsi }_{N}({\varvec{v}}_{i}) + {{\varvec{w}}}^{(\mathbb {P})}_{iN}\) for every \(i<N\). Using Eq. 23 and Proposition 1, we have:
Finally, we can compute the strength distribution in a closed form. The following theorem provides the strength distribution of a PBEM model:
Theorem 2
(Strength Distribution) For the complete weighted graph\({{\mathbb {G}}}\) evolved with PBEM, the distribution of the global strengthk follows a power law with exponent\(-3\):
Simulation Validation Next, we provide a simulation to validate the analytical results on the strength distribution of both DBEM and PBEM models. We initiate a complete graph with \(10^4\) nodes and random weight adjacency. This network is then evolved under the dynamical processes of both DBEM and PBEM models. The strengths of nodes in the equilibrium point of the evolved networks are extracted, and their distribution is illustrated in Fig. 1. As can be seen, the DBEM model is generating an exponential strength distribution (i.e., a straight line in semilogarithmic plot), while PBEM model produces a power-law strength distribution (i.e., a straight line in log–log plot).
Fig. 1
DF and CCDF of strengths in DBEM model and PBEM models. It is clear that DBEM generates an exponential strength distribution, while PBEM produces a power-law strength distribution. a Exponential strength DF and CCDF of DBEM Model in Semi-Log Scale. b Power-law strength DF and CCDF of PBEM Model in Log-Log Scale
×
6 Network properties
In this section, we introduce and analyze two important properties of weighted networks for each of the DBEM and PBEM models. First, we introduce the distance between individuals and study the distribution of Geodesic distance in networks, and second, we analyze closeness centrality in networks evolving according to the proposed models.
6.1 Geodesic distance
Geodesic distance is an important property in social networks Freeman (1978), Kretschmer (2004), Leskovec et al. (2008). To measure the Geodesic distance, we first need to introduce a measure of distance between two connected individuals. This is defined as the inverse of link weights:
if \(i\ne j\), \(a_{ij}=1\) and \(d_{ii}=0\) for every i. To illustrate, let \(w_{ij}\) denote the number of times individual i is co-observed with individual j. Then, the more these two individuals are seen together the closer they are in the network (i.e., \(d_{ij}\) is smaller).
While, \(d_{ij}\) represents the distance between two individuals that are directly connected in the network, we can also define the Geodesic path between two individuals as the path with the minimum sum of distances. The length of a Geodesic path is called the Geodesic distance. In large-scale networks, the average Geodesic distance is expected to be short compared to the number of nodes and the direct distances between individuals. To better understand this phenomenon, next, we calculate the Geodesic distance between two arbitrary individuals in a complete hierarchical network that is evolved under either DBEM or PBEM models.
6.1.1 Geodesic distance in DBEM
Let \(d^G_{ij}\) be the Geodesic distance between individuals i and j. The following theorem states that in a complete hierarchical network evolved based on DBEM, the Geodesic path between individuals i and j is their direct connection and the Geodesic distance \(d^G_{ij} = d_{ij}\).
Theorem 3
In a complete hierarchical network evolved based on DBEM, the geodesic distance\(d^{s}_{ij}\)between the\(i{\hbox {th}}\)and\(j{\hbox {th}}\)individuals is equal to the distance associated with the connection between them:
The proof of the above theorem can be attained by contradiction. Without loss of generality, assume \(i>j\), and thus \(d_{ij} = i-1\) (see Eq. 15). Suppose that the Geodesic path starts from \(i{\hbox {th}}\) individual and crosses a third individual k with \(k \ne i,j\). The distance \(d_{ik}\) can be determined as:
We know that the Geodesic distance is equal to the sum of distances on the Geodesic paths. Therefore, \(d^G_{ij} > d_{ik}\). Using Eq. 35, it can be easily seen that \(d^G_{ij}> i-1 > j-1\). Hence, the direct connection between two individuals has a shorter distance that the Geodesic distance. Thus, the supposition is false, and the shortest path can not pass any third individual. This completes the proof of the above theorem. \(\square\)
6.1.2 Geodesic distance in PBEM
In contrast to DBEM, in which the Geodesic path between two individuals is the direct link connecting them, the following theorem shows that in PBEM, the Geodesic path always passes through the first individual in a complete hierarchical network:
Theorem 4
In a complete hierarchical network evolved based on DBEM, the Geodesic distance\(d^{s}_{ij}\)between the\(i{\hbox {th}}\)and\(j{\hbox {th}}\)individuals, for\(i\ne j\)is
The proof follows again by contradiction. Without loss of generality, we assume that \(i>j\). Suppose there exists individuals i and j for which \(d^G_{ij} = d_{ij}\), then:
Therefore, every direct link between two individuals can be replaced via a path that passes through the first individual. Hence, the supposition is false completing the proof. \(\square\)
The distribution of Geodesic distances for individuals in DBEM and PBEM for a network of \(10^4\) nodes (as studied in Fig. 1) is illustrated in Subfig. 3a, b. Subfig. 3c illustrates the changes in average of weighted Geodesic distances in networks of different sizes.
Fig. 2
Weighted Geodesic Distance in DBEM- and PBEM-based complete networks. a In a DBEM-based evolved network, the Geodesic distance between individuals at the bottom of the hierarchy quickly increases; b in the PBEM-based evolved network, the Geodesic distance has a distribution close to normal; c in the PBEM-based evolved networks, the number of hops in the Geodesic path between individuals is always equal to 1 or 2, but the length of this path gradually increases by the increase in size of network a DBEM Model, b PBEM Model, c PBEM Model
×
6.2 Closeness centrality
In this subsection, we study the closeness centrality of individuals in complete hierarchical networks. The closeness centrality of \(i{\hbox {th}}\) individual, \(c_i\), is defined as the inverse of the sum of its Geodesic distance to other individuals:
Thus, the lower the total Geodesic distance of one individual from other nodes is, the more central the individual. Given the different distribution of Geodesic distances produced by DBEM and PBEM models, we also expect to see different profiles in the centrality of nodes. Next, a detailed study of this measure for each of these networks is presented.
6.2.1 Closeness centrality in DBEM
Using Theorem 3, the closeness centrality for individual i in a complete hierarchal network, evolved based on DBEM, is given as below.
The above equation allows us to measure centrality of each individual in a DBEM network, in closed form.
6.2.2 Closeness centrality in PBEM
In contrast to DBEM, in which the Geodesic path between two individuals is the direct connection between them, in Theorem 4, we saw that the Geodesic path in PBEM-based networks always passes through the first individual who is at the top of the hierarchy. Therefore, the Geodesic distance \(d^{s}_{ij}\) between two individuals is given by Eq. 36. The closeness centrality for \(i{\hbox {th}}\) individual is then:
By replacing \(d_{i1}\) and \(d_{j1}\) from Eq. 37 into Eq. 43, the closeness centrality for PBEM can be attained in closed form.
The closeness centrality of individuals in DBEM and PBEM for a network of \(10^4\) nodes is illustrated in Fig. 3. This centrality measure is normalized in a way such that the maximum closeness becomes 1. As can be seen, in DBEM, the individuals centrality decreases much slower compared to that in PBEM.
Fig. 3
The normalized closeness centrality of DBEM and PBEM networks
×
7 Real-world verification
In this section, we use real-world interaction networks to validate the proposed DBEM and PBEM models for networks with arbitrary hierarchical structures. Next, we introduce the data sets used for this study.
7.1 Data setup
For verification of the proposed DBEM and PBEM processes, we use four real-world social network datasets: (1) Howler Monkey Groups, (2) Kangaroos, (3) Wolf Dominance, and the (4) US Airports networks.
Howler Monkey Groups (Howler Monkey Groups 2015)—This dataset represents the social network among mantled howler monkeys, Alouatta palliata, which is collected by Froehlich and Thorington (1981) and Sailer and Gaulin (1981). The dataset represents the co-observations in a group of 17 monkeys, where the co-observations of every two monkeys are reported in form of a weighted adjacency matrix.
Kangaroos (Kangaroo 2015; Grant 1973)—This dataset represents the social network among free-ranging gray kangaroos. A weighted adjacency matrix shows the number of observed physical proximities among a group of 17 kangaroos. Observations were collected in the Nadgee Nature Reserve in New South Wales.
Wolf Dominance (van Hooff and Wensing 1987; Wolf Dominance 2015)—This dataset represents the social network among a captive family of 16 wolves in Arnheim, Germany. A weighted adjacency matrix shows the number of occasions on which the row wolf was seen to exhibit a “low posture” display directed toward the column wolf, which is a sign of fear and being subordination.
US Airports (Us airports network dataset 2015; Opsahl 2011)—This dataset presents the flights between 1574 US airports in 2010. The elements of the weighted adjacency matrix shows the number of flights from the row airport to the column airport in 2010. In this paper, we consider the first 200 airports with highest overall number of flights. Besides, we set the number of flights between two airports equal to the average of each flight from one to the other. This way, the adjacency matrix becomes symmetric, thus compatible with the experimental method introduced next.
In each of the aforementioned datasets, the adjacency and weight matrices are denoted by \({\mathbb {A}}^d = [a^d_{ij}]\) and \({\mathbb {W}}^d = [w^d_{ij}]\).
7.2 Experiment methodology
Although, in all four interaction networks Howler Monkey Groups, Kangaroo, Wolf Dominance, and the US Airports, the interactions between every two nodes are available, except for the Wolf Dominance network, no hierarchy is explicitly given for the other three networks. The methodology used to compare the interaction networks with PBEM and DBEM is given as:
Extraction of hierarchy— In many real-world networks, the interactions frequency/strength between individuals are reported, while the hierarchy (i.e., details of who initiates or dominates in the interaction) is not revealed. However, as shown in this paper, extraction of hierarchies in the network plays a crucial role in understanding the underlying mechanism of interactions.
The linear hierarchies and dominance orders in social networks are studied by many researchers e.g., in Appleby (1983), Vries (1995), Vries (1998), Shizuka and McDonald (2012), Sales-Pardo et al. (2007). In most of these studies, authors assume existence of data in form of frequencies of wins and loses of the same dyad member for each pair of individuals. Unfortunately, this is not the case for the three networks under study in this paper, Howler Monkey Groups, Kangaroo and the US Airports, and many other real-world networks.
Therefore, we rather use a simple yet efficient technique to extract the hierarchy of the network. Namely, we assume the nodes with more interactions are higher in the hierarchy. Therefore, we rank the nodes based on the sum of interaction frequencies exhibited by each node. Then, for every pair of nodes i and j that \(a^d_{ij}=1\) and rank of i is higher than j the tuple (j, i) is added to hierarchy set \({\mathbb {H}}\).
Evolving the models based on hierarchy set—Once the hierarchy set \({\mathbb {H}}\) is extracted from an interaction network, both proposed models, DBEM and PBEM, can be easily evolved using the dynamical system in (11) and (20), respectively. Each model results in a set of interaction weights and consequently node strengths.
Normalization of the interaction matrix— The dynamical models of DBEM and PBEM generate normalized weight matrices \({\mathbb {W}}\) where the sum of interaction weights between i and all its superordinate j is equal to 1. Therefore, we use the following rule to acquire a normalized weight matrix \({\mathbb {W}}^{d(n)} = [w^{d(n)}_{ij}]\):
Next subsection, presents the comparison of generated models by DBEM and PBEM to normalized real-world networks.
7.3 Results
To compare the estimations of DBEM and PBEM with data from real-world networks, we first compute the absolute strengths in each real-world network by using the normalized Weight matrix \({\mathbb {W}}^{d(n)}\). The absolute strength of each node is then estimated using the DBEM and PBEM models, based on the corresponding hierarchical structure of each real-world network.
We use Kolmogorov–Smirnov to test the equality of the distribution of the node strengths in real-world networks and the estimations of these strengths computed by the proposed models in this paper. Table 1 provides the p value of the Kolmogorov–Smirnov test for the real-world datasets. As can be seen, for the Howler Monkey Groups dataset, the p value of DBEM estimation has a larger value compared to the PBEM estimations. For the other datasets, the pvalues of PBEM estimations have larger values. Therefore, we assume that the network interactions in the first network are evolved based on only dominance of individuals, while the other three networks follow a Prestige-based evolution model. In all four datasets, the Kolmogorov–Smirnov test accepts the null hypothesis that both sets are drawn from the same distribution at the 5\(\%\) significance level.
Table 1
p value of the Kolmogorov–Smirnov test for predictions made by DBEM and PBEM models
Howler monkey groups
Kangaroos
Wolf dominance
US airports
DBEM
0.93
0.67
0.63
0.06
PBEM
0.67
0.73
0.99
0.23
A large value of p supports the hypothesis that the distribution of estimated values is similar to the distribution of real-world values
Figure 4 illustrates the CCDF of strengths in the real-world datasets. Estimations by DBEM, for the Howler Monkey Groups are shown in Fig. 4a, and estimations by PBEM, for the other datasets are shown in Fig. 4b–d.
Fig. 4
Estimation of the strength CCDF in real-world networks by DBEM in a and PBEM in b–d. While the prestige does not play an important role in the social network of monkeys (a), the co-observation of Kangaroos (b), the mocking battle among Wolves (c) and the traffic between top 200 US airports (d) is highly influenced by the prestige of each member in the network
×
To measure the accuracy of estimations of DBEM and PBEM models, illustrated in Fig. 2, we perform a statistical analysis of the absolute difference between estimated intensity of edges and their real intensity for each of the four real-world networks. The average estimation errors are 0.081 for Howler Monkey Groups estimated by DBEM (and 0.120 for its estimation with PBEM), 0.070 for Kangaroos estimated by PBEM (and 0.086 for its estimation with DBEM), 0.080 for Wolf Dominance estimated by PBEM (and 0.096 for its estimation with DBEM), and 0.027 for the US Airports estimated by PBEM (and 0.030 for its estimation with DBEM). The distribution of errors based on their minimum, first quartile, median, third quartile, and maximum are shown in Fig. 5. The pairwise statistical comparisons between these four distributions show significant differences (p value is less than \(10^{-5}\) for all four comparisons, using the Kolmogorov–Smirnov test). Such significant difference can be explained by the difference in hierarchical structures of each real-world network.
Fig. 5
Statistical comparison of the absolute difference between estimated weight of edges and their real weight for four real-world networks. The median of errors are 0.065, 0.050, 0.046 and 0.012 for Howler Monkey Groups, Kangaroos, Wolf Dominance and the US Airports networks, respectively
×
7.4 Time complexity
In this subsection, we study the time complexity of the proposed evolutionary models. Firstly, it should be considered that for the complete hierarchical networks that were studied in Sects. 4, 5, 6 the properties of each network can be calculated in closed form. For instance, the expected global strength or closeness centrality of an individual i in a PBEM-based evolved network can be directly calculated by Eqs. 29 and 43. Such closed form expressions can be efficiently computed for any network with any size. For the general case of incomplete networks, however, the equilibrium of each model should be computed by evolving the dynamical model, introduced in (10), based on the underlying rules of either Eq. (11), or Eq. (11).
To perform a study reflecting the running times of the proposed models, we ran a variety of simulations. All simulations were run on an iOS with a 2.9 GHz Intel Core i7 processor and 8GB RAM, with MATLAB R2014b. The time steps used for running the discretized version of (10) were chosen to \({\Delta } t = 0.1\). The dynamical model was considered to be at equilibrium when the error condition \(e(t) = ||{{\varvec{w}}}||_2<0.01\) was satisfied.
In practice, it turns out that both DBEM and PBEM models have very close convergence rates. Therefore, we study the amount of time required for the PBEM model on a set of randomly generated small-world and scale-free networks. The size of networks vary from 20 nodes to 10,000 nodes, and every network has an average degree of 4. For each network size, we generate 50 networks, where the scale-free networks follow the preferential attachment model provided in Barabási and Albert (1999), and the small-world networks follow the algorithm given in Watts and Strogatz (1998) with rewiring probability 0.1. The results are illustrated in Fig. 6.
Fig. 6
Time complexity of the PBEM model for networks of size 20 to 10,000 nodes in logarithmic scale for y-axis. The simulation of a network with 1000 nodes converges to equilibrium in 3.4 min for a small-world network of average degree 4 and in 7.6 min for a scale-free network with average degree of 4
×
According to the results provided in Fig. 6, the time complexity of PBEM model for a small-world network can be represented as \(T(n)={\mathcal {O}}(n^2)\). Although, the running time of this model for very large networks (e.g., 1,000,000 nodes) can be relatively high, in contrast to the stochastic models, this model requires just one run of the simulation to get to the final equilibrium and computations of all characteristics of the network. Also, the use of parallel processing can be beneficial in decreasing the running time for very large networks.
7.5 Network assortativity
The assortativity property of networks measures the preference of network nodes to attach to other nodes that are similar in terms of degree or strength where the latter is applicable for weighted networks Newman (2002), Leung and Chau (2007), Xie et al. (2007). As the models proposed in this work generate weighted networks, we use the average nearest neighbor strength measure for this purpose. Let \({\varPsi }_{nn}(v_i)\) be the average strength of nearest neighbors of ith node as
This value can be averaged over classes of nodes with strength \(\mathbf {\varPsi }\) and be represented as \({\varPsi }_{nn}(\mathbf {\varPsi })\) that can provide a probe of correlation between strength of neighboring nodes. If \({\varPsi }_{nn}(\mathbf {\varPsi })\) is an increasing function of \(\mathbf {\varPsi }\), then nodes with similar strengths tend to establish ties with high intensity and otherwise nodes with dissimilar strengths tend to establish strong ties.
Subfigure 7a–d illustrates the average nearest neighbor strength for four different networks all with 1000 nodes and average degree 4. Subfigure 7a, b corresponds to two networks evolved via DBEM model over hierarchical networks with small-world and scale-free structures, respectively. As can be seen, in the small-world subfigure, DBEM shows an assortative behavior in which the nodes with high intensity have a higher average strength of nearest neighbor compared to the nodes with lower strength. In the scale-free network, \({\varPsi }_{nn}\) is a decreasing function for low degree nodes and an increasing function for high degree nodes. The assortativity of networks evolved based on PBEM model are shown in Subfig. 7a, b; the PBEM model shows assortative behavior (i.e., increasing \({\varPsi }_{nn}\)) in the small-world network and shows disassortative behavior (i.e., decreasing \({\varPsi }_{nn}\)) in the scale-free network.
Fig. 7
Assortativity in networks evolved based on DBEM and PBEM models. All subfigures are plotted in log–log scale for networks of 1000 nodes and average degree 4. While both models generate assortative behavior in an small-world network, the PBEM model generates disassortative behavior in scale-free network, and DBEM model generates a mixed behavior (i.e., first decreasing and then increasing \({\varPsi }_{nn}\)) in the scale-free network a Small-world network (DBEM), b scale-free network (DBEM), c Small-world network (PBEM), d scale-free network (PBEM)
×
As can be seen in Subfig. 7a–d, the assortativity of the networks evolved based on DBEM and PBEM models highly depends on the underlying structure of these networks.
8 Discussion
Distinguishing the role of dominance and prestige in evolution of social networks is a difficult task. To illustrate, consider the perspective of van Vugt and Tybur (2015) who believe that dominance is very common among non-human primates where members of the social group achieve priority through threat and intimidation. In contrast, they believe prestige is more specific to humans and is granted to individuals because they help other individuals achieve their goals. In a different context, Ridley (1994, Chapter 5), refers to the behavior of hens in Lek and explains that “it hardly matters whether the male chosen is the best male; what counts is that he is the most fashionable.” In other words, Ridely sees the high status (i.e., being fashionable) of some birds a more important criterion than their dominance in reaching more popularity.
The proposed two analytical models in this paper allow us to mathematically distinguish the behaviors of dominance-based and prestige-based evolving networks. Although the models are simple, they illustrate how a minor change in evolution of the network can result in fundamental differences in the network’s behavior. Theorems 1 and 2 illustrate a major difference in distribution of individuals’ interaction intensities. Additionally, Theorems 3 and 4 analyze the Geodesic distance of individuals and reveal how in prestige-based evolving networks a central hub is formed where all shortest paths in the network pass this hub. In contrast such hubs are not seen in dominance-based evolving networks. By considering the beneficial role of hubs in complex networks Newman (2008), Guimera et al. (2005), Heuvel and Sporns (2013), Theorems 3 and 4 can shed some light on evolutionary foundations in adoption of prestige-based strategies in some species.
Finally, the real-world validations not only verify the correct estimation of DBEM and PBEM models, but also introduce a new method to distinguish between dominance-based and prestige-based evolving networks. As shown in Sect. 7.3, the co-observation of monkeys in a group highly depends on the dominance of each individual, while interactions among a group of kangaroos and a group of wolves and traffic between US airports follows the prestige-based dynamic rules.
9 Conclusion
In this paper, we proposed two dynamical models for hierarchical networks which evolve based on dominance or prestige of the individuals. Although the dynamical system for each of these models was designed based on simple hierarchical rules, for the special case of complete graphs, the derived stationary points had been shown to recover the exponential (Theorem 1) and power-law strength distributions with exponent -3 (Theorem 2), respectively. Networks with such strength distributions, specifically the latter distribution, were shown to be efficient in sharing of resources and robust to random failures. Therefore, emergence of such strength distributions despite the simple hierarchical structure could explain how hierarchical social structures have survived among social beings.
As another contribution, for the special case of complete graphs, we defined and derived the Geodesic distance and closeness centrality metric in closed form. This was used to assess the importance of nodes in hierarchical networks. Our distance measure reflected that in dominance-based networks the shortest path between every two member was their direct link (Theorem 3), while in prestige-based hierarchies, every shortest path was passing through the member with highest “prestige” (Theorem 4). Finally, for the general case of any hierarchical network, we validated the estimations generated by the models through data gathered from real-world networks. This validation not only verified the predictions of DBEM and PBEM, but also introduced a way to distinguish between networks that evolve based on either dominance or prestige. Our studies on the proposed models, showed that they have subquadratic time complexity with respect to the size of network and were capable of generating either assortative or disassortative network behavior depending on the underlying hierarchy of the network.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
