The Game-Theoretic Interaction Index on Social Networks with Applications to Link Prediction and Community Detection

1 Introduction

Vertex similarity is a fundamental network concept extensively studied in the literature [Blondel et al., 2004; Jeh and Widom, 2002]. An effective measure of node-similarity allows for solving various real-life problems: establish trustbase recommendation [Hang and Singh, 2010], detect similar genes [Bass et al., 2013], or recover damaged network [Chen et al., 2012]. Two particularly interesting problems that are highly relevant to social networks are: (1) link prediction [Leicht et al., 2006] and (2) community detection [Fortunato, 2010]. Specifically, the former problem involves estimating the likelihood of having a link between a given pair of nodes, based on the observed links and the attributes of nodes. The latter problem involves identifying groups of nodes such that there are relatively many links among nodes of the same group, and relatively few links among nodes belonging to different groups. Both problems are relevant to various fields in which graph representations are common, including sociology [Girvan and Newman, 2002] and computer science [Misra et al., 2012].

There are two general classes of similarity measures: (1) local, and (2) global. The first class focuses on a local neighbourhood of the nodes in question (i.e., the nodes between which we are determining whether a link exists). Conversely, the second class considers the entire network. While global measures generally yield better qualitative results, they are more computationally involved, which limits their applicability to smaller networks. In contrast, local measures are scalable-they can be used even for very large networks. Thus, in this paper, we focus on local similarity measures.

The majority of local similarity measures are built upon the following concept: the more common neighbours two nodes share, the more similar those nodes are. This reasoning can be also extended to the entire neighbourhood of both nodes, or, in other words, their spheres of influence. Thus, similarity is proportional to the overlap of spheres of influence.

In this paper, we extend the above notion of similarity, building upon the game-theoretic interaction indexa concept developed in coalitional game theory and fuzzy systems to measure the interaction between a pair of elements embedded in a larger set of elements [Owen, 1972; Murofushi and Soneda, 1993; Grabisch and Roubens, 1999].

The basic form of the interaction index is built upon two well-known solution concepts from game theory-the Shapley value [Shapley, 1953b] and the Banzhaf index [Banzhaf, 1965]. It is also generalized to a wider class of solution concepts called semivalues [Grabisch and Roubens, 2000].

Our methodology may be summarised as follows. We first construct a coalitional game in which players are nodes in the network and the payoff of a coalition is a function of its sphere of influence parametrized by k, where k is the degree of influence. Given this influence game, we use the above interaction index to measure the similarity between the spheres of influence of any two nodes, given all the possible coalitions that those two nodes belong to.

Interestingly, despite the interaction index being hard to compute in general, we show that, in our influence game, it is computable in polynomial time. Specifically, the algorithm we propose for computing semivalue interaction indices runs in O(|V |2 ) time, after precomputations requiring O(|V ||E|+|V |2 ). Better still, this polynomial-time result can be further improved upon if we reduce the scope of interaction in the network (defined by parameter k), or if we focus on the Shapley value-based interaction index. In the latter case computing similarities between two nodes requires O(|V |) time, and this complexity is the same as for the fastest local similarity measures in literature. Overall, in the worst case scenario our link prediction and community detection algorithms based on the Shapley value-based interaction index run in O(|V |3 ) time.

We use our algorithm to study a number of real-life networks, and show that the interaction index-based similarity measure outperforms the other local measures in solving the link prediction and community detection problems.

2 Preliminaries

Let N = {1, 2, . . . , n} be the set of players. A characteristic function, ν, assigns a real value (or payoff ) to every coalition of players: ν : 2N → R, with ν(∅) = 0. A tuple (N, ν) is called coalitional game.

Semivalues: One of the fundamental problems in cooperative game theory is how to evaluate the importance or contribution of players in a coalitional game. Semivalues represent an important class of solutions to this problem [Dubey et al., 1981]. To define semivalues, let us first denote by MC(C, i) the marginal contribution of the player i to coalition C, i.e., MC(C, i) = ν(C ∪ {i}) - ν(C). Furthermore, let α : {0, 1, . . . , |N| - 1} → [0, 1] be a discrete probability distribution. Intuitively, α(k) is the probability that a coalition of size k is drawn from the set of all possible coalitions. Now, given a function α, the semivalue φv(ν) of a player i in the cooperative game ν is:

where C l is the random variable that corresponds to a coalition being drawn with uniform probability from the set of all coalitions of size l in the set of players N \ {i}, while E[·] is the expected value operator. For instance, some prominent semivalues include the Shapley value [Shapley, 1953a] and the Banzhaf index [Banzhaf, 1965]-two solution concepts widely studied in cooperative game theory due to their various desirable properties [Maschler et al., 2013].

Interaction index: To understand the notion of the interaction index, we have to first introduce the definition of synergy between two players in cooperative games. It is the additional value (either positive or negative) that these players achieve by cooperating. Formally: S(i, j) = ν({i, j}) - ν({i}) - ν({j}). Similarly, the synergy between i and j with respect to a coalition C is:

The notion of interaction among entities, or "players", builds upon the above notion of synergy. Apart from game theory, it has been studied in various other fields, such as fuzzy systems, multi-criteria decision making, aggregation function theory, statistics and data analysis [Marichal and Mathonet, 2008]. Informally, the value of interaction among a group of players is the average synergy of this group over all coalitions they could potentially belong to. In this paper we focus on the semivalue interaction index between two players, which is defined as follows:

Definition 1 The semivalue interaction index in (N, ν) is:

where β : {0, 1, . . . , |N| - 2} → [0, 1] is a discrete probability distribution and E[S(Cl , i, j)] = ∑C∈{C⊆N\{i,j} : |C|=l} S(C,i,j) (|V |-2 l ) .

The interpretation of these index is as follows: a) if Iij < 0 then i and j have an overall negative influence on each other, b) if Iij > 0 then i and j have an overall positive influence on each other, c) if Iij = 0 then i and j do not influence each other, or their influences cancel out. Generally, if Iij is very high, or low, the players interact between themselves intensively. The three semivalue interaction indices widely studied in literature are: Shapley interaction index [Grabisch, 1997] (β(l) = 1/(|V | - 1)), Banzhaf interaction index [Roubens, 1996] (β(l) = (|V |-2 l )/2|V |-2 ) and chaining interaction index [Marichal and Roubens, 1999] (β(l) = 2(l+1) (n-1)(n-2) ).

3 Our Model

In this section we describe our approach to define new similarity function. First, we introduce the influence games that underpin the interaction index. Next, we define our key concept-the semivalue k-steps interaction index defined on networks. Finally, we translate desirable properties of this index from game-theory to the network context.

Influence games: Michalak et al. (2013b) studied a number of coalition games defined on networks, in which the characteristic function evaluates each subset of nodes proportionally to the size of the sphere of influence that this subset has in this network. If we denote the sphere of influence of the set C ⊆ V as SF(C) ⊆ V then:

Definition 2 The influence game of a graph G = (V, E) is a tuple (G, νG), where νG : 2V → R is an influence function such than for each C ⊆ V we have νG(C) = SF(C).

In this paper we focus on the k-steps influence function.

Definition 3 The k-steps influence function is:

where d(v, u) is the distance between two nodes and d(S, v) = minu∈S d(u, v).

The interaction index on networks: In further sections we use the following interaction index in order to measure similarity between nodes in networks:

Definition 4 The semivalue k-steps interaction index is a tuple (G, νk), where G = (V,E), νk is the k-step influence function, and the interaction between any two nodes u, v ∈ V is given by Iuv(V, νk).

The properties: Now, we translate the game-theoretic axiomatization of the semivalue interaction index to the network context [Grabisch and Roubens, 1999].

Property 1 Interaction between nodes is symmetric. That is, ∀v,u∈V Iuv = Ivu.

Property 2 If a node always contributes its singleton value to any community, then its interaction is always zero: 1 ∀C⊆V\{v} MC(C, v) = νG({v}) =⇒∀u∈V\{v} Ivu = 0.

1 Intuitively, if a node always contributes the same, its sphere does not overlap with that of any coalition, and so it is considered to have zero interaction with others.

Property 3 If two influence functions are combined into one νG = ν ′G + ν ′′G then Iuv(νG)=Iuv(ν ′G)+Iuv(ν ′′G).

Property 4 If two nodes contribute the same value to all communities then they have the same interaction: ∀C⊆V\{v,u} MC(C, v)=MC(C, u) =⇒∀w∈V\{v,u} Ivw = Iuw.

4 Computing interaction index on networks

In this section, we tackle the problem of computing the ksteps semivalue interaction index on large networks. Despite the exponential space of all subsets of nodes in the network, we present a combinatorial analysis that results in an algorithm capable of measuring the interaction between any two nodes in polynomial time. Our analysis is motivated by the work done by Szczepa´nski et al (2015), who defined the class of polynomial-time computable game-theoretic network centralities. Here, we focus on equation (2). More specifically, for each pair of nodes v, u ∈ V we will show how to compute E[S(Cl , v, u)]-the expected value of their synergy with respect to the random set C l . Our main observation is that this computation comes down to computing the expected marginal contribution of v, and of u, to C l . Formally:

Before presenting our main theorem, we need additional notation. For every node v ∈ V , let Nk(v) denote the set of nodes reachable from v with at most k steps, and let degk(v) denote the number of such nodes. Formally, Nk(v) = {u ∈ V | d(v, u) ≤ k∧v ̸= u} and degk(v) = |Nk(v)|. We extend this notation to sets of nodes. That is, Nk(C) = ⋃v∈C Nk(v) \C and degk(C) = |Nk(C)|. Now, we are ready to introduce the following theorem:

Theorem 1 Given a graph, G, and a pair of nodes u, v ∈ V , the k-steps semivalue interaction index between u and v can be computed in time polynomial in |V |.

Proof: Let us focus on one of the two nodes, say v, and analyse its marginal contribution to C l ⊆ V \ {v, u}. In this analysis, we will first focus on the cases where the marginal contribution is positive, and then move our attention to the cases where it is negative. Regarding the case of positive marginal contribution, when v joins C l , such a contribution is only made with the help of another node n ∈ Nk(v) where n is not in C l nor is it accessible within k steps from C l . Such a contribution is indeed positive because the node n is not under the influence of coalition C l but under the influence of coalition C l ∪ {v}. Moving on to the case of negative marginal contributions, such a case only happens when v is accessible within k steps from C l . This is because the coalition C l has influence on the node v while the coalition C l ∪ {v} has no influence. In order to formalize the above observations, we introduce two Bernoulli random variables. The first one, denoted by B+ l,v,n , indicates whether the node v makes a positive marginal contribution through node n to the random set C l . Formally, we have:

where P[·] denotes probability, and E[·] denotes expected value. The second one, denoted by Bl,v , indicates whether the node v makes a negative marginal contribution through itself to the random set C l . More formally:

Now, we will use a combinatorial argument to compute the probabilities in equations (5) and (6). For the sake of clarity we will assume that (ab) = 0 for a < b and that for any a we have a0 = 0. Recall that there are exactly (|V |-2 l ) possible sets C l . With this in mind, we will start by showing how the probability in (5) is computed. Here, we will focus on the following two complementary cases:

• Case 1: n ∈ (Nk(v) \ {u}) such that n ̸= u and u /∈ Nk(n). In this case, the probability in (5) can be computed as follows:

The nominator of the above fraction indicates that, in order to satisfy the condition (Nk(n) ∪ {n}) ∩ C l = ∅, we can choose any of the nodes in V \ {u, v} except those that are in n ∪ (Nk(n) \ {v}) .

• Case 2: n ∈ (Nk(v) \ {u}) such that n = u or u ∈ Nk(n). In this case, since we have u /∈ C l , the probability in (5) is computed differently as follows:

By combining the above two cases, for v and any n ∈ Nk(v) we obtain:

Having shown how to compute E[B+ l,v,n ], we now move to E[Bl,v ]. In particular, we show how to compute the probability in (6). To this end, observe that P[Nk(v) ∩C l ̸= ∅] = 1-P [Nk(v)∩C l = ∅]). Based on this, instead of focusing on the probability of the event Nk(v) ∩C l ̸= ∅, we focus on the probability of the complementary event, i.e., Nk(v)∩C l = ∅, as this simplifies our analysis. Using the same combinatorial argument as before, we obtain the following for v:

The final formula for E[MC(Cl , v)] combines equations (7) and (8). That is,

So far, we have shown how to compute one of the three expressions in equation (4), namely E[MC(Cl , v)]. Moving on the expression E[MC(Cl , u)] in (4), this can be computed in exactly the same manner. Finally, the third expression in (4), i.e., E[MC(Cl , {u, v})], is computed slightly differently. For each n ∈ Nk({u, v}) we have:

and we also have:

Finally, we can combine all equations in order to compute the expected synergy:

The above formula can be used to compute E[S(Cl , u, v)] in polynomial time. Therefore, the k-steps semivalue interaction index between v and u can be computed in time polynomial in |V | using equation (2), which ends our proof. □

4.1 Algorithm

Algorithm 1 directly implements expression (2). The expected value operator E[S(Cl , u, v)] is computed using equation (12). It computes the k-steps semivalue interaction index for a given pair of nodes u, v ∈ V in the graph G. This algo-

Algorithm 1: k-steps semivalue interaction index

rithm requires some precomputations. For each node u ∈ V we need to calculate Nk(u). We can store these values using O(|V |2 ) space and perform these precomputations in O(|V |(|V | + |E|)) time using breadth-first search. After this precomputation, the algorithm itself runs in O(|V |2 ) time. Our algorithm can be easily adapted to weighted graphs; the only difference is that the precomputations should be carried out using the Dijkstra algorithm (which takes O(|V |(|E| + |V | log |V |)) time). The algorithm itself remains unchanged.

Algorithm 2: k-steps Shapley interaction index

Input: Graph G = (V, E), nodes v, u ∈ V

Data: for each node u ∈ V :

Nk(u) - the set of k-Neighbours

Output: Iku,v k-steps Shapley value interaction index 1 ISV,k u,v ← 0;

We note that our algorithm can be optimized for any specific semivalue interaction index. For instance, Algorithm 2 is a version of our algorithm that computes the k-steps Shapley value interaction index in O(|V |) time.

Our final observation is that Algorithms 1 and 2 always result in non-positive values of interaction between nodes. This is due to the fact, that our coalitional game defined on graph (G, νk) is weakly subadditive, that is in our game only negative synergies can occur. So, the more negative value ISV,k u,v is, the more similar nodes u and v are.

5 The Performance of Interaction Index

In this section, we evaluate the effectiveness of our similarity measure based on the Shapley k-steps interaction index. More specifically, we compare it against the other measures from Table 1, which are all based on both the topology of the network (known as structural similarities) and local information (known as local similarities) [L¨u and Zhou, 2011]. In all of these measures, a parameter k is used to define the influence of v, denoted by Nk(v). This is simply the set of nodes that are k steps away from v in the network. That is to say, every node v is assumed to have k degrees of influence. In our experiments we test Shapley value-based interaction index as it is the most prominent semivalue and it has been already widely studied in the context of social networks [Michalak et al., 2013b; Szczepa´nski et al., 2014].

5.1 Link Prediction

Having proposed a new algorithm for computing vertex similarity, in this subsection we show how to use it to solve the link prediction problem on various real-life networks.

Link prediction and similarity measure: We evaluate the effectiveness of each similarity measure using the following standard procedure for solving the link prediction problem: given a graph G with missing or not-yet-developed edges, the procedure invovles two steps: (i) compute the similarity of each pair of nodes that have no edge between them, and (ii) connect the most similar pairs.

Experiment: Our experiment was performed on seven popular real-life networks. 2 The basic idea is to remove some edges from the network under consideration, then test the effectiveness of each similarity measure in predicting where the missing edges should be. More specifically, the settings were as follow:

• We randomly remove 40%3 of edges from the original graph G = (V,E), thus obtaining the training graph GT = (V, ET ).
• For each node v ∈ V we create 8 × 3 different rankings based on 8 similarity measures (the Shapley k-steps interaction index , and the seven measures from Table 1) and k ∈ {1, 2, 3}. Specifically, for each such configuration, we rank all nodes that are not directly connected to v. Then, we take the number of missing edges, i.e., degG(v) - degGT (v), from the top of the ranking, and compute the precision. The AUC [L¨u and Zhou, 2011] is computed for the entire ranking.
• For each of the real-world networks in our experiments, the above process is repeated 30 times, and the average precision and AUC is computed.

Table 2 presents the results of the experiment. Here, the bold text highlights the best performance out of all measures. As can be seen, our new measure SvII outperforms the others on most networks.

Interestingly, although our measure is very similar to the Resource Allocation measure (RA) [Zhou et al., 2009], ours

2 All datasets are at http://konect.uni-koblenz.de/networks/.

3 Lower percentages 20% and 10% were also tested resulted in higher precision and AUC and similar performance rankings.

34

34

Figure 1: Dendrograms of the Zachary karate club network for k = 2 and k = 3, respectively.

dominates RA on all networks. Perhaps the reason behind this difference is the following: when measuring the similarity between v and u, the RA measure assumes that node v sends some resource to u through a common neighbor n ∈ Nk(u)∩Nk(v), who simply divides this resource equally among the nodes in Nk(n), meaning that u recieves exactly 1 degk(n) of the resource. On the other hand, when using our measure, the fraction in formula (12) is 1 deg(n)-1 , not 1 deg(n) , which may indicate that the node n does not send back any of the resource to the sender, v. Another difference compared to the RA measure is that, with our measure, if nodes u and v happen to be within each others' sphere of influence, i.e., u ∈ Nk(v), then they can transmit resource directly to each other (see formula (12) and Algorithm 2).

5.2 Community detection algorithm

In this subsection we show how to use our interaction index to identify communities.

Hierarchical clustering: The effectiveness of each similarity measure is evaluated using the following standard procedure for detecting communities: starting with |V | communities, each containing a single node, the algorithm proceeds by (i) merging the two most similar communities, and (ii) evaluating the modularity [Newman, 2006] of the resulting community structure. This procedure of merging communities and evaluating modularity is repeated until we end up with a single community containing all nodes. Finally, the community structure with the highest modularity is chosen. We will refer to this procedure as the bottom-up hierarchical clustering algorithm, or simply clustering algorithm, for community detection. Note that step (i) requires measuring the similarity between two groups of nodes, not two individual nodes as is the case with all aforementioend measures of similarity. To address this issue, we generalize each measure based on the notion of complete linkage (furthest-neighbour) [Jain et al., 1999], which basically states that an individual should not join a community if his interaction with any of the community members is too small. We are looking for communities containing tightly connected nodes and this is exactly done by complete linkage: "The complete-link algorithm produces tightly bound or compact clusters" [Jain et al., 1999] Other popular linkage types, namely single linkage and average linkage, were also tested. However, the complete linkage proved to yield the best results for all the similarity measures.

The above community detection algorithm runs in O(|V |2 log |V |) time, provided that the similarity between each pair of nodes has been precomputed, which takes O(|V |3 ) time regardless of the measure used.

Next, we perform two experiments. In the first, we evaluate the sensitivity of the clustering algorithm to the parameter k when using our Shapley k-steps interaction index. In the second experiment, we evaluate the effectiveness of our measure, compared to those in Table 1, in terms of the modularity of the resulting community structure.

Experiment 1: the parameter k. Generally speaking, our measure, as well as any of the other measures from Table 1, can be controlled by the parameter k, which specifies the degree of influence in the network. This is particularly useful for community detection, as it allows for controlling the size of the resulting communities. In other words, by using any such measure, we obtain a multi-resolution method [Fortunato, 2010]. We analyze the outcome given different values of k and given our measure of similarity: if k is too small, then some potentially important interactions may not be detected. On the other hand, if k is too large, the interaction between weakly related nodes may negatively affect the clustering process.

Let us illustrate what happens when k is too large on the widely studied friendship network of the Zachary karate club [Zachary, 1977]. Figure 1 presents the hierarchical clustering of this network. We observe that for k = 3 the dendrogram has fewer levels compared to k = 2. This means that, for k = 3, in each step of the clustering process, the interaction computed between many pairs of clusters (possibly single nodes) is the same. Thus, for this network, k = 3 is too high, and results in a lower modularity compared to k = 2.

Next, let us consider what happens when k is too small. In Figure 2 we can see two community structures for the Political Books network, in which an edge between two books indicates that they were co-purchased by the same buyer on Amazon [Krebs, 2004]. For k = 2 we obtained a division into two communities: (roughly speaking) books supporting government in one community, and criticising it in the other. However, if we set k = 1 we obtain a division into 12 communities. This latter community structure turns out to be much worse in terms of modularity than the former one.

Generally speaking, it certainly helps the algorithm to try out all possible k and choose the one that yields the best community structure. However, this increases the computational complexity, and slows down the algorithm especially given large networks.

Experiment 2: performance. Now, the performance of the clustering algorithm given our similarity measure is compared against its performance given other measures from Table 1. Importantly, the ground-truth community structure is unknown for all networks considered in this experiment, with the only exception being the Zachary network. Therefore, following the standard practice in the literature, the quality of any given community structure will be measured using modularity [Newman, 2006].

The results are reported in Table 3. The table also reports the coverage [Brandes and Erlebach, 2005] of the selected community structure, which simply measures the ratio between intra-edges (those within a community) and inter-edges (those between communities). As can be seen, for most of the networks, the clustering algorithm using our similarity measure (SvII) gives the best results. Once again, ours dominates the Resource Allocation (RA) measure on all datasets. The second best measure is Leicht-Holme-Newman Index (LHN) [Leicht et al., 2006]. It gives high similarity to nodes that have many common neighbors compared to the expected number of such neighbors.

6 Summary &FutureWork

In this paper we proposed a new vertex similarity measure based on the game-theoretic notion of the interaction index. Despite the computational challenges posed by the combinatorial nature of this measure, we showed that, given our influence game, it is possible to compute this index in polynomial time. We tested our measure on two important applications: link prediction and community detection. For both applications, our measure outperformed other alternatives from literature.

While in this work we focused on one particular influence game, it would be interesting to study other, perhaps more involved but still polynomially-computable ones like those based on betwenness centrality [Szczepa´nski et al., 2012] or connectivity games [Michalak et al., 2013a]. Furthermore, while we focused on standard games, it would be interesting to study interaction index defined for generalized coalitional games [Michalak et al., 2014] but extended to graphs.

Acknowledgments

Piotr Szczepa´nski was founded by the Polish National Science Centre based on the decision DEC2013/09/N/ST6/04095. Tomasz Michalak was supported by the European Research Council under Advanced Grant 291528 ("RACE")