A “network” consists of a crowd of actors and a set of binary relations that tie pairs of actors. Networks are pervasive in the real world. Nature, society, information, and technology are supported by ostensibly different networks that in fact share an amazing number of interesting structural properties.
Key Insights
- Networks are everywhere; they are indeed the fabric of nature, society, information, technology, and sometimes even of art. All we need is an eye for them.
- The notion of centrality claims central actors are connected with central others, a mantra repeated over the past 70 years in econometrics, sociometry, bibliometrics, and information retrieval.
- Power, on the other hand, claims that powerful actors are connected with powerless others; it is meaningful in, say, bargaining situations, where it is favorable to negotiate with those with few options.
Networks are modeled in mathematics as “graphs,” with actors represented as points (also called nodes or vertices) and relations depicted as lines (also called edges or arcs) connecting pairs of points. In this article, we focus on undirected graphs, where the edges do not have a particular orientation. A meaningful question on networks is: Which are the most central (important) nodes? Many measures have been proposed to address it. Among them, “eigenvector centrality” (or simply centrality in this article) states that an actor is central if it is connected with central actors. This circular definition is captured by an elegant recursive equation
where x is a vector containing the sought centralities, A is a matrix encoding the network, and λ is a positive constant. Two actors in a network that are tied by an edge are said to be neighbors. Equation (1) claims two important properties of centrality: the centrality of an actor is directly correlated with the number of its neighbors and the centrality of its neighbors. Central actors are those with many ties or, for an equal number of ties, central actors are those connected with central others. This intriguing definition has been discovered and rediscovered many times over in different contexts. It has been investigated, in chronological order, in econometrics, sociometry, bibliometrics, Web information retrieval, and network science; see Franceschet12 for an historical overview.
In some circumstances, however, centrality—the quality of being connected to central ones—has limited utility in predicting the locus of “power” in networks.2,8,11 Consider exchange networks, where the relationship in the network involves the transfer of valued items like information, time, money, or energy. A set of exchange relations is positive if exchange in one relation promotes exchange in others and negative if exchange in one relation inhibits exchange in others.7 In “negative exchange networks,” power comes from being connected to those with few options. Being connected to those with many possibilities reduces one’s power. Think of, for instance, a social network in which time is the exchanged value. Imagine every actor has a limited time to listen to others and that each actor divides its time among its neighbors. Exchange of time in one relation clearly precludes exchange of the same time in other relations. Which actors receive the most attention? They are the nodes that are connected to many neighbors with few options, since they receive almost full attention from all their neighbors. On the other hand, actors connected to few neighbors with many options receive little consideration because their neighbors are mostly busy with others.
In this article, we propose a theory on power in the context of networks. We start by this thesis: An actor is powerful if it is connected to powerless actors. We implement this circular thesis through this equation
where x is the sought power vector, A is a matrix encoding the network, and x÷ is the vector whose entries are the reciprocal of those of x. Equation (2) states two important properties of power: the power of an actor is directly correlated with the number of its neighbors and is inversely correlated with the power of its neighbors. The first property seems reasonable; the more ties an actor has, the more powerful the actor is. The second property characterizes power; for an equal number of ties, actors linked to powerless others are powerful. On the other hand, actors tied to powerful others are powerless.
Central actors are those with many ties or, for an equal number of ties, central actors are those connected with central others.
We investigate the existence and uniqueness of a solution for Equation (2), exploiting well-known results in combinatorial matrix theory. We study how to regain the solution when it does not exist, by perturbing the matrix representing the network. We formally relate the introduced notion of power with alternative notions and empirically compare them on the European natural gas pipeline network.
Motivating Example
In his seminal work on power-dependence relations, from 1962, Richard Emerson11 claimed that power is a property of the social relation, not an attribute of the person: “X has power” is meaningless, unless we specify “over whom.” Power resides implicitly in others’ dependence, and dependence of an actor A upon actor B is directly proportional to A’s motivational investment in goals mediated by B and inversely proportional to the availability of those goals to A outside the A-B relation. The availability of such goals outside that relation refers to alternative avenues of goal achievement, most notably through other social relations.11 This type of relational power is endogenous with respect to the network structures, meaning it is a function of the position of the node in the network. Exogenous factors (such as allure or charisma) external to the network structure might be added to endogenous power to complete the picture.
We begin with some small archetypal examples typically used in exchange-network theory to informally illustrate the notion of power and sometimes to distinguish it from the intersecting concept of centrality.10 Consider a two-node path
The situation is perfectly symmetric, and a reasonable prediction is that both actors have the same power. In a three-node path
much is changed. Intuitively, B is powerful and A and C are not. Indeed, both A and C have no alternative venues besides B (both depend on B), while B can exclude one of them by choosing the other.a In a four-node path
actors B and C hold power, while A and D are dependent on either B or C. Nevertheless, the power of B is less here than in the three-node path; in both cases, A depends on B, but in the three-node path, C also depends on B, while in the four-node path, C has an alternative, node D. Hence, node B is less powerful in the four-node path with respect to the three-node path since its neighbors are more powerful. Finally, the five-node path
is interesting since it discriminates power from centrality. All traditional central measures (eigenvector, closeness, betweenness) claim that C is the central one. Nevertheless, B and D are reasonably the powerful ones. Again, this is because they negotiate with weak partners (A and C or E and C), while C bargains with strong parties (B and D). This example is useful for illustrating an additional subtle aspect of power. Notice that in both the five-node path and the four-node path, B is surrounded by nodes (A and C) that are locally similar; for instance, they have the same degree in both paths. However, the power of C is reasonably less in the five-node path than in the four-node path; hence, we might expect the power of B is greater in the five-node path with respect to the four-node path. This separation is possible only if the notion of power spans beyond the local neighborhood of a node, if, say, power is recursively defined.
As a larger and more realistic example, consider Figure 1, which depicts the European natural gas pipeline network. Nodes are European countries (country codes according to ISO 3166-1), and there is an undirected edge between two nations if a natural gas pipeline crosses the borders of the two countries. Data has been downloaded from the website of the International Energy Agency (http://www.iea.org). The original data corresponds to a directed, weighted multigraph, with edge weights corresponding to the maximum flow of the pipeline. We simplified and symmetrized the network, mapping the edge weights in a consistent way.
This is a negative exchange network because the exchange of gas with a country precludes the exchange of the same gas with others. Intuitively, powerful countries are those that are connected with states with few options for exchanging the gas. Suppose country B is connected to countries A and C, and B is the only connection for them, or A–B–C. Countries A and C can sell or buy gas only from B, while country B can choose between A and C. Reasonably, the bargaining power of B is greater, which traduces in higher revenues or less expense for B in the gas negotiation.
A Theory on Power
Let G be an undirected, weighted graph. The graph G may contain “loops,” or edges from a node to itself. The edges of G are labeled with positive weights. Let A be the adjacency matrix of G; that is, Ai,j is the weight of edge (i,j) if such edge exists and Ai,j = 0 otherwise. Hence, A is a square, symmetric, nonnegative matrix. Loops in G correspond to elements in the main diagonal of A.
The “centrality problem” is as follows: find a vector x with positive entries such that
where λ > 0 is a constant. This means λxi=ΣjAi,jxj, that is, the centrality of a node is proportional to the weighted sum of centralities of its neighbors. This is the main idea behind PageRank, Google’s original webpage ranking algorithm. PageRank determines the importance of a webpage in terms of the importance assigned to the pages that hyperlink to it. Besides Web information retrieval, this thesis has been successfully exploited in disparate contexts, including bibliometrics, sociometry, and econometrics.12
We define the “power problem” as follows: find a vector x with positive entries such that
where we denote with x÷ the vector whose entries are the reciprocal of those of x. This means xi=ΣjAi,j/xj; that is, the power of a node is equal to the weighted sum of reciprocals of power of its neighbors. Notice that if λx = Ax÷, then, setting
, we have that y = Ay÷; hence, the proportionality constant λ is not necessary in the power equation. This notion of power is relevant on negative exchange networks.2,8 In these networks, when a value is exchanged between actors along a relation, it is consumed and cannot be exchanged along another relation. Hence, important actors are those in contact with many actors with few exchanging possibilities.
Finally, the “balancing problem” is the following: find a diagonal matrix D with positive main diagonal such that
is doubly stochastic; that is, all rows and columns of S sum to 1. The balancing problem is a fundamental question that is claimed to have first been used in the 1930s to calculate traffic flow4 and since then has been applied in many disparate contexts.14
It turns out that the power problem is intimately related to the balancing problem. Given a vector x, let Dx be the diagonal matrix whose diagonal entries coincide with those of x. We thus have the following result.
THEOREM 1. The vector x is a solution of the power problem if and only if the diagonal matrix Dx÷ is a solution for the balancing problem.
PROOF. If DAD is doubly stochastic, then DADe = e and eT DAD = eT, where e is a vector of all 1s. Actually, since A and D are symmetric, it holds that DADe = e ⇔ eT DAD = eT. If the vector x does not have zero entries, then Dx is invertible and Dx−1 = Dx÷. We have that
Existence and unicity of a solution. The link between the balancing problem and the power problem we established in Theorem 1 allows us to investigate a solution of the power problem (Equation 4) using the well-established theory of matrix balancing.
Recall that the “diagonal” of a square n × n matrix is a sequence of n elements that lies on different rows and columns of the matrix. A permutation matrix is a square n × n matrix that has exactly one entry equal to one in each row and each column, while all the other entries are equal to zero. Each diagonal clearly corresponds to a permutation matrix where the positions of the diagonal elements correspond to those of the unity entries of the permutation matrix. In particular, the identity matrix I is a permutation matrix, and the diagonal of A associated with I is called the main diagonal of A. A diagonal is positive if all its elements are greater than 0. A matrix A is said to have “support” if it contains a positive diagonal and is said to have “total support” if A ≠ 0 and every positive element of A lies on a positive diagonal. Total support clearly implies support.
A matrix is “indecomposable (irreducible” if it is not possible to find a permutation matrix P such that
where X and Z are both square matrices and 0 is a matrix of 0s; otherwise A is “decomposable (reducible).” A matrix is “fully indecomposable” if it is not possible to find permutation matrices P and Q such that
where X and Z are both square matrices; otherwise, A is “partly decomposable.” Clearly, a matrix (fully indecomposable) is also irreducible. It also holds that full indecomposability implies total support.5 Moreover, the adjacency matrix of a bipartite graph is never fully indecomposable, while the adjacency matrix of a non-bipartite graph is fully indecomposable if and only if it has total support and is irreducible.9 We say a graph has support, has total support, is irreducible, and is fully indecomposable if the corresponding adjacency matrix has these properties.
The combinatorial notions just outlined are rather terse. Fortunately, most of them have a simple interpretation in graph theory. It is known that irreducibility of the adjacency matrix corresponds to connectedness of the graph. Moreover, given an undirected graph G, let us define a “spanning cycle forest” of G a spanning subgraph of G whose connected components are single edges or cycles, including loops that are cycles of length 1. It is easy to realize that there exists a correspondence between diagonals in the adjacency matrix and spanning cycle forests in the graph. Hence, a graph has support if and only if it contains a spanning cycle forest and total support if and only if each edge is included in a spanning cycle forest. Four examples are given in Figure 2.
The following is a well-known necessary and sufficient condition for the solution of the balancing problem.9,17
THEOREM 2. Let A be a symmetric nonnegative square matrix. A necessary and sufficient condition for the existence of a doubly stochastic matrix S of the form DAD, where D is a diagonal matrix with positive main diagonal, is that A has total support. If S exists, then it is unique. If A is fully indecomposable, then matrix D is unique.
It follows that the power problem x = Ax÷ has a solution on the class of graphs that has total support. Moreover, if the graph is fully indecomposable, then the solution is also unique.
Perturbation (regaining the solution). What about the power problem on graphs whose adjacency matrix lacks total support? For such graphs, the power problem has no solution. Nevertheless, a solution can be regained by perturbing the adjacency matrix of the graph in a suitable way. We investigate two perturbations on the adjacency matrix A
- Diagonal perturbation:
= A + αI, where α > 0 is a damping parameter and I is the identity matrix. - Full perturbation:
= A + αE, where α > 0 is a damping parameter and E is a full matrix of all 1s.
Matrix
is clearly fully indecomposable, has total support, and is irreducible. Hence, the power problem (as well as the centrality problem) on a fully perturbed matrix has a unique solution. On the other hand, matrix
has total support. Indeed, if Ai,j > 0 and i = j, then the main diagonal Ak,k for 1 ≤ k ≤ n is positive and contains Ai,j. If i ≠ j, then the diagonal Ai, j, Ak, k for 1 ≤ k ≤ n and k ≠ i,j is positive and contains Ai,j. The power problem on a diagonally perturbed matrix thus has a solution. Moreover, the solution is unique if A is irreducible, since it is known that for a symmetric matrix A it holds that A is irreducible if and only if A + I is fully indecomposable.6 Interestingly, the diagonal perturbation, besides providing convergence of the method, is useful for incorporating exogenous power in the model. By setting a positive value in the ith position of the diagonal, we are saying that node i has a minimal amount of power, or not a function of the position of the node in the network. We can thus play with the diagonal of the adjacency matrix to assign nodes with potentially different entry levels of exogenous power.
Intuitively, the diagonal perturbation is less invasive than its full counterpart; the former modifies the diagonal elements only, and the latter touches all matrix elements. But how invasive is the perturbation with respect to the resulting power? To investigate this issue, we computed the correlation between original and perturbed power solutions. A simple and intuitive measure of the correlation between two rankings of size n is Kendall rank correlation coefficient k, which is the difference between the fraction of concordant pairs c (the number of concordant pairs divided by n(n – 1)/2) and that of discordant pairs d in the two rankings: k = c − d. The coefficient runs from –1 to 1, with negative values indicating negative correlation, positive values indicating positive correlation, and values close to 0 indicating independence. We used the following network datasets: a social network among dolphins, the Madrid train bombing terrorist network, a social network of jazz musicians, a network of friendships between members of a karate club, a collaboration network of scholars in the field of network science, and a co-appearance network of characters in the novel Anna Karenina by Lev Tolstoj.
The main outcomes of the current experiment are as follows (see Figure 3): as soon as the damping parameter is small, both diagonal and full perturbations do not significantly change the original power; power with diagonal perturbation is closer to original power than power with full perturbation; and the larger the damping parameter, the lower the adherence of perturbed solutions to the original one.
Computing power. Due to the established relationship between the balancing problem and the power problem, we can use known methods for the former in order to solve the latter. The simplest approach for solving Equation (4) is to set up the iterative method
known as the Sinkhorn–Knopp method (SKM).17 If we set x0 = e, the vector of all 1s, then the first iteration x1 = Ae; that is, x1(i)=ΣjAi, j is the degree di of i. The second iteration x2 = A(Ae)÷; that is, x2(i)=Σj Ai, j/di is the sum of reciprocals of the degrees of the neighbors of i.
If A has total support, then the SKM converges, or, more precisely, the even and odd iterates of the method converge to power vectors that differ by a multiplicative constant. The convergence is linear with a rate of convergence that depends of the sub-dominant eigenvalue of the balanced matrix S = DAD (see Theorem 2).17 In some cases, however, the convergence can be very slow. Knight and Ruiz14 proposed a faster algorithm based on Newton’s method (NM) that we now describe according to our setting and notations. In order to solve Equation (4), we apply NM for finding the zeros of the function f: ℝn → ℝ n defined by f(x) = x − Ax÷. It is not difficult to check that
where δi,j. = 1 if i = j and δi,j = 0 otherwise. We collect these partial derivatives in the Jacobian matrix of f that turns to be
where the squaring of x is to be intended entrywise. Formally, the NM applied to the equation f(x) = 0 becomes
To apply NM precisely it is necessary to solve a linear system at each step, but this would be too expensive. Nevertheless, an approximate solution of the system obtained by means of an iterative method is sufficient, giving rise to an inner–outer iteration. This approach is appealing when the matrix that has to be balanced is symmetric and sparse, which is the case for the power problem on real networks.14
We experimentally assessed the complexity of computation of power on the real social networks; in fact, we used the largest biconnected component for the first three networks in order to also work with totally supported graphs. We use both SKM and NM. We consider the computation on the original matrix, as well as on the perturbed ones. We use as a benchmark the complexity of the computation of centrality using the power method (PM). The complexity is expressed as the overall number of matrix-vector product operations. If a matrix is sparse (the case for all tested networks), such operation has linear complexity in the number of nodes of the graph. The main empirical findings are summarized as follows (see Table 1): SKM on the original matrix is significantly slower than PM, and diagonal perturbation does not significantly change its speed; full perturbation significantly increases the speed of SKM, so the complexity of SKM with full perturbation and that of PM are comparable (moreover, the larger the damping parameter, the faster the method); NM on the original matrix is much faster than SKM: its complexity is comparable to that of fully perturbed SKM and PM; and NM with diagonal perturbation is even faster than NM, and the larger the damping parameter, the faster the method.
Relationship with alternative power measures. Bonacich2 proposed a family of parametric measures depending on two parameters: α and β. If A is the adjacency matrix of the graph, the Bonacich index x is defined as
The index for a node is the sum of two components: a first one (weighted by the parameter α) depends on the node’s degree, and a second one (weighted by the parameter β) depends on the index on the node’s neighbors. From Equation (6), under the condition that I – βA is not singular, it is possible to obtain the following explicit representation of the proposed measure
The equivalence with the infinite sum holds when |β| < 1/r, where r = maxi|λi|, with λi. the eigenvalues of A; that is, r is the spectral radius of A. When the parameter β is positive, the index is a centrality measure. In particular, the measure approaches eigenvector centrality as a limit as β approaches 1/r. On the other hand, when β is negative, the index is a power measure; it corresponds to a weighted sum of odd-length paths (with positive sign) and even-length paths (with negative sign).2 Hence, powerful nodes correspond to nodes with many powerless neighbors. Finally, when β = 0, the measure boils down to degree centrality.
The difficulty with this measure is that it is parametric; that is, it depends on parameters α and β. While it is simple to set the parameter α, and it can be used to assign exogenous power to nodes, the choice for the parameter β is more delicate. In particular, the index makes sense when the parameter |β| < 1/r, hence the spectral radius r must be computed or at least approximated.
The precise relationship between Bonacich power (Bonacich index with negative β) and power defined in Equation (4) is explained as follows: If we set x0 = (1/γ)e in Newton’s iteration for the computation of power described earlier we obtain
But this first approximation is a member of the family of Bonacich’s measures, with α = 2γ and β = –γ2. Since β is negative, we indeed are facing a measure of power. Hence, Bonacich power can be considered as a first-order approximation of power using NM.
Bozzo et al.3 investigated power measures on sets of nodes. Given a node set T let B(T) be the set of nodes whose neighbors all belong to T. Notice that nodes in B(T) do not have connections outside T, hence are potentially at the mercy of nodes in T. We define a power function p such that p(T) = |B(T)| – |T|. Hence, a set T is powerful if it has potential control over a much larger set of neighbors B(T). The power measure is interpreted as the characteristic function of a coalition game played on the graph and the “Shapley value” of the game; or the average marginal contribution to power carried by a node when it is added to any node set is proposed as a measure of power for single nodes. Interestingly, the discovered game-theoretic power measure corresponds to the second iteration of SKM for the computation of power as defined by Equation (4); that is, to the sum of reciprocals of neighbors’ degrees.
The power of an actor somewhat inversely depends on the power of its neighbors.
The study of power has a long history in economics (in its recognition of bargaining power) and sociology (in its interpretation of social power).10 Consider the most basic case where just two actors, A and B, are involved in a negotiation over how to divide one unit of money. Each actor has an alternate option—a backup amount it can collect in case negotiations fail, say, α for A and β for B. A natural prediction, known as “Nash’s bargaining solution,”15 is that the two actors will split the surplus s = 1 – α – β, if any, equally between them; that is, if s < 0 no agreement between A and B is possible, since any division is worse than the backup option for at least one of the parties. On the other hand, if s >= 0, then A and B will agree on α+s/2 for A and β+s/2 for B.
A natural extension of the Nash bargaining solution from pairs of actors to networks of actors was proposed in Cook et al.8 and Rochford16 and further investigated, particularly in Bayati et al.1 and Kleinberg et al.13 In the following, we describe the dynamics that capture such an extension. Let A be the adjacency matrix of an undirected, unweighted graph G. Hence, Ai,j = 1 if there is an edge (i,j) in G and Ai,j = 0 otherwise. Negotiation among actors is possible only along edges; each pair of actors on an edge negotiates for a fixed amount of €1, and each actor may conclude a negotiation with at most one neighbor (one-exchange rule). For every edge (i,j) define
- Ri,j as the amount of “revenue” actor i receives in a negotiation with j.
- Li,j as the amount of revenue actor i receives in the best alternative negotiation, excluding the one with j.
Notice that matrices R and L have the same zero-non-zero pattern as A. More precisely, consider the following iterative process. We start with
for all edges (i,j) and
elsewhere. Let N(i) be the set of neighbors of node i. For t > 0, the best alternative matrix L(t) at time t is
Let the surplus
be the amount for which actors i and j will negotiate at time t; notice that actor i will never accept an offer from j less than his alternate option
, and actor j will never accept an offer from i less than her alternate option
The profit matrix R(t) at time t is then
Notice that
that is,
and
is the Nash’s bargaining solution of a negotiation between actors i and j, given their alternate options
and
Let R be the fixpoint of the iterative process R(t) for growing time t. The “Nash power” xi of node i is the best revenue of actor i among its neighbors; that is
Among many other attractive results, Bayati et al.1 showed that the dynamics always converge to a fixpoint solution. Nash power bears some analogy with the one we propose and investigate here; in particular, both notions share the same recursive powerful-is-linked-with-powerless philosophy. Nash power for an actor i depends directly on the revenues of i among its neighbors, which directly depend on the alternate options of i among its neighbors, which inversely depends on the revenues of neighbors of i, which determine the power of neighbors of i. Hence, power of an actor somewhat inversely depends on the power of its neighbors.
Using Kendall correlation, we assessed the overlapping of power, as defined in this article, with centrality and degree, as well as Bonacich power (Bonacich index with negative parameter β), Shapley power (the sum of reciprocals of neighbors’ degrees), and Nash power on the social networks mentioned earlier. The main empirical outcomes are summarized in the following (see Table 2): as expected, both power and centrality are positively correlated with degree, but power is negatively correlated with centrality when the effect of degree is excluded (we used partial correlation); power is positively correlated with Bonacich power, and the association increases as the parameter β declines below 0 down to –1/r, with r the spectral radius of the adjacency graph matrix (moreover, the association is greater when the adjacency matrix is perturbed); power is positively correlated with Shapley power, and the association is generally stronger than with Bonacich power; and power is positively correlated with Nash bargaining network power, but the strength of the correlation is generally weaker than with Shapley power and Bonacich power. In particular, we noticed that the Nash-based method maps the power scores of the nodes of the surveyed networks into a small set of values, with very high frequency for values close to 0, 0.5, and 1. Hence, it is difficult to discriminate different gradations of power for nodes.
Motivating Example Reloaded
Here, we revisit examples from the “Motivating Example” section, using them as a benchmark to compare the different notions of power described in the “Relationship with Alternative Power Measures” section. When the graphs are not totally supported (all cases but the two-node path), we used diagonal perturbation with damping 0.15 to obtain a solution. Moreover, we set Bonacich index parameters α = 1 and β = –0.85/r, where r is the spectra radius of the graph.
In the two-node path, all methods agree to give identical power to both nodes. In the three-node path A–B–C, all methods agree B is the powerful one. Notably, Nash power assigns all power (1) to B and no power (0) to A and C, while the other methods say A and C hold a small amount of power. In the four-node path A–B–C–D, all methods claim B and C are the powerful ones. Moreover, all methods recognize that the power of B in this instance is less than its power in the three-node path. Finally, in the five-node path A–B–C–D–E, all methods discriminate B and D as the most powerful nodes, followed by C and finally A and E, with the only exception of Nash power, which assigns all power (1) to B and D and null power (0) to all other nodes; hence, the central node C has the same power as the peripheral nodes A and E, according to this method. All methods, with the exception of Shapley, notice that the power of B is greater in the five-node path with respect to the three-node path. This is because Shapley is a local method, while the others are global (recursive) methods.
Let us now revisit the natural gas pipeline example. We ranked all countries according to the following power and centrality measures: Shapley power (S), Bonacich power (B), power as defined in this article (P), Nash power (N), and eigenvector centrality (C). Table 3 shows the corresponding Kendall correlation matrix. As expected, P is well correlated with its approximations B and S. Moreover, P is positively correlated with N, but the correlation strength is weaker. Also, the association between P and C is positive but weak and mostly explained by the association with degree of both measures. Indeed, if we exclude the effect of degree, this correlation is negative.
These associations are mirrored in the top-10 rankings and ratings listed in Table 4, as well as in the scatter-plot comparing power and centrality in Figure 4. Notice how Germany (DE) is both powerful and central; Italy (IT) and Turkey (TR) are powerful but not central; Norway (NO) is central but not powerful; and there are many countries that are neither powerful nor central outside the rankings. For instance, Italy contracts with nations that are both powerless and peripheral, namely Austria, Switzerland, Croatia, Tunisia, Libya, and Slovenia, with only Austria included in the top-10 power list and only Austria and Switzerland included in the top-10 centrality list (not in the first positions). The ranking according to Nash power is somewhat unusual if compared with the other power measures; for instance, Germany has bargaining power 0.5 and only in 14th postion, tied with the other countries. It is fair to note that the generalized Nash bargaining solution was originally proposed in the context of assignment problems (such as in matching apartments to tenants and students to colleges) and was not suggested as a rating-and-ranking method for nodes in a network. For instance, in balanced matching over the gas network, Italy preferably negotiates with Libya and Turkey with Georgia. In fact, Cook and Yamagishi8 proposed using the negotiation values obtained by each node in such a solution as a structural power measure; see also Easley and Kleinberg10 (chapter 12) for a similar interpretation. According to the experiments we conducted for this article, this interpretation might seem opinable, but further investigation is necessary to gain a solid conclusion.
Conclusion
We proposed a theory on power in the context of networks. The philosophy underlying our notion of power maintains that an actor is powerful if it is connected with many powerless actors. This thesis has its roots and applications mainly in sociology and economics and traces an historical parallel with its celebrated linear counterpart, namely eigenvector centrality.12
The virtues of our definition of power are: it is a simple, elegant, and understandable measure; it is theoretically well-grounded and directly related to the well-studied balancing problem, making it possible to borrow results and techniques from this setting; the formulation is not parametric; and it is global (the power of a node depends on the entire network) and can be approximated with a simple local measure—the sum of reciprocals of node degrees—that has a game-theoretic interpretation and can be efficiently computed on all networks. The definition has limitations as well, mainly that an exact solution exists only on the class of totally supported networks and is not immediately normalizable, so care is needed when comparing power values for nodes in different networks.
Figures
Figure 1. The European natural gas pipeline network.
Figure 2. (top left) The graph has no support since a spanning cycle forest is missing. (top-right). The graph has support formed by edges (1, 4) and (2, 3), but the support is not total; (edges (1, 3) and (1, 2) are not part of any spanning cycle graph. (bottom left) The graph has total support but is not irreducible, hence is not fully indecomposable. (bottom right) The graph has total support and is irreducible and not bipartite, so is fully indecomposable.
Figure 3. Correlation between original and perturbed powers varying the damping parameter from 0 to 1 on the largest biconnected component of the social network among dolphins (which has total support). The horizontal line corresponds to the correlation with diagonal perturbation and maximum damping. The correlation on the other networks is similar.
Figure 4. Scatterplot of power versus centrality. Vertical and horizontal lines correspond to third quartile.
Tables
Table 1. Complexity of computation of power with different methods: PM (benchmark); SKM (SKM without perturbations for totally supported networks); SKM-D (SKM with diagonal perturbation and damping 0.15); SKM-F (SKM with full perturbation and damping 0.01); NM (NM without perturbations for totally supported networks); and NM-D (NM with diagonal perturbation and damping 0.15).
Table 2. Correlation of power, as defined in this article, with degree (D), centrality (C), Bonacich power (B), Shapley power (S), and Nash power (N).
Table 3. Matrix of correlations among power and centrality measures.
Table 4. The top 10 powerful and central countries in the European natural gas exchange network.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment