The main purposeof this research is to investigatethe possibility to apply exact and approximate Shapley values in the assessment of centrality measures of nodes in networks.

The key advantage of as a centrality measure is that it detects the most influential nodes among all subgroups of nodes, i. e. everybody prefers to be in a group with the most pivotal node than with anyother node.

To apply this theory let us consider graph where is a set of nodes, and is a set of edges. A classical definition of the Shapley value in terms of graphsis

, (1)

· is a subset of nodes

· is a monotonous function of asubset of nodes

· is a contribution of node to subset

An equivalent formula for is

, (2)

· is a permutation of all nodes in a graph,

· is a set of all permutations of a set of nodes

· is a node with position in permutation

· is a subset of nodes .

The main challenge here is that a direct calculation of requires the enumeration of all nonempty subsets of nodes for the formula (1) or permutations for the formula (2) which are computationally intensive tasks. For that reason approximation method of calculation based on random permutations is used. Then approximate is

(3)

· is a permutation of all nodes in a graph,

· is some set of permutations

· is a fixed number of permutations in

o means that all permutations are enumerated and

· is a node with position in permutation

· is a subset of nodes .

For each node the algorithm selects subsets of nodes that are onthe left side of node in every permutation. This means that the contribution of node into random subsetsis calculated and then the average of these contributions is taken.

Here two loops occur: one is on nodes and the other one is on permutations. Evidently, it is more rational to make the outer loop on permutations and then calculate for each permutation. Consequently, the algorithm is as follows:

· Fix a number of random permutations

·

· For each permutation :

network shapley value

o Move from to

o For each node calculate ;

o was calculated during the previous step

o Update

o Cumulate

· Normalize to the number of permutations .

The question about the accuracy of calculation may arise here. There can be different criteria of the accuracy, for example, metric criteria, where is a vector of approximation Shapley values, is a vector of exact Shapley values, is some metric, is a threshold. But in terms of centrality measures the order of values is usually required; this means that rank criteria can be used here, where is some rank correlation measure (Kendall correlation, Spearman correlation, etc.). But due to the fact that exact values are unknownthe ranks of approximation values that consider and permutations should be compared until rank correlation tends to level off. Levelling-off of ranks means that adding more permutations into calculation willchange ranks insignificantly. The last notice can be regarded as criteria for the estimation of optimal number of permutations in the following way:

Giventhreshold and thelevel of reliability is consequently estimated until the correlation exceeds times running; then the optimal number of permutations .

Evidently, when threshold is considered some of the ranks are still not stable. Hence, for the calculation of final ranks the median of all ranks from to can be calculated. The median value allows us to escape random jumps in ranks.

Additionally, tracks of node's ranks can be drawn by memorizing them on previous steps.

Table2. Capacities of subgraphs.

Then, exact Shapley values are:

.

Hence, a final vector of Shapley values is:

.

A vector of final ranks of Shapley values is: .

We can see that if we delete node 1 then we arestill able to reach every node from any point; hence, node 1 is the least powerful in this system. Alternatively, node 2 contains many paths over all subsets and this results inthe fact that node 2 is the most powerful and guarantees the stability of a system.

If the approach of formula (3) is used then inmost cases all permutations are considered because exact differs by small values for nodes 2, 3,5. However, for some order of permutations less than 90 permutations for exact ranks estimation is required.

Evidentially, the number of simple paths can be enormous. Consider a complete graph with n nodes. Then, for any two nodes and the number of paths between them is equal to. If all pairs of nodes in a complete graph are considered, then the number of simple paths is , which is a huge number even for small n. Hence, some approximation algorithms are proposed. There are variousways of simplifying the model. One of the approaches is based on the limitation of the maximal length of a path; hence, paths that are not greater than some predefined limit are considered:

, (5)

· || is a function of the length of a path;

· L is the maximal path length.

Formula (5) still requires the enumeration of all simple paths (with the limitation on the length) which is a computationally complex issue. Due to this fact,this function is applied to small graphs (with 20 nodes).

To provide a thoughtful analysis of this approach based on formula (4) and its analogue (5) exact (without limitations) has been calculated, the ranks of exact with approximation based on formula (5) have been compared. The accuracy (rank correlation) of calculations is analyzed with respect to the limitation on path length. The criteria for the considered number of permutations is , where , is an optimal number of permutations. Figure 2 provides rank correlations of exact and with different parameter L calculated with random permutations:

Table 3. Top-10 nodes by and with different L.

It can be concluded that L does not influence the accuracy (i. e. high values of L do not guarantee exact results). Hence, parameter Lcan be limited by small value and get another interpretation for top nodes, for example, top nodes are pivotal in its vicinities of radius L. It should be noted that the same value ofL for subgraphs of all sizes is fixed; hence, in small subgraphs all paths are considered.

The study also provides a representative analysis of the proposed method (see example below). The following criteria of accuracy of rank definition is used:

,

where . This example considers the maximal lengths of path at Italso tracks fluctuations of correlation measures and ranks of nodes (Figures 4-5) depending on the considered number of permutations. Moreover, with classical centrality measures are compared (Tables 4 - 7).

Example Network 1:

Table 4. Graph characteristics.

Table 5. Top-5 nodes by Sv and classical centralities.

Table 6. Kendall rank correlation.

Table 7. Spearman rank correlation.

The optimal number of permutation is The number of subgraphs is equal to . The algorithm considers approximately subgraphs.

The second approach is also based on all simple paths enumeration. But here the length of paths is considered in the following way

, (6)

· is a simple path between nodes ;

· is a set of all simple paths between nodes ;

· || is a function of the length of a path.

Definitely, instead of the inverse length of a path the price for the length can have another form of a decreasing function, for example, etc. In this work only function (7) is analyzed.

The most powerful nodes here represent major hubs. Such approach can be applied to the transportation systems where we want to minimize a path length but if one of the ties or a group of ties are “out of work” we are ready to pay for an alternative (more distant) route.

Let us consider Example 1. The results are as follows (computational calculation): .

Here node 1 improved its position in the system and node 4 worsened it. The reason is that node 4 is mainly achieved through long paths and doesn't provide short passages. Conversely, despite the fact that node 1 is unreachable it provides many short passages, so it contributes more in subgraphs than node 4.

Apparently, distant nodes add rather long paths than short paths, which leads to the fact that their contribution to subsets should be less than the contribution of central (hub) nodes in some cases. Hence, the inverse length of a path is considered to decrease the importance of long paths and increase the importance of short paths. Additionally, with a limitation on the length of a path added and with only short paths taken into consideration, the contribution of central nodes will be generally more significant. Moreover, such limitation permits us not to enumerate all paths between pairs of nodes, which is a computationally complex issue. So, the capacity function looks like

,(7)

where is a limitation on the length of a path (small value).

Moreover, another approximation method can be implemented here. This approach is based on a random choice of paths between pairs of nodes with the limitation on the length of a path. Then, the capacity function looks like

,(8)

where is some random subset of all possible paths between nodes x and y. The number of paths that are considered can be taken as some fraction of the estimation of the number of paths between two nodes in a subgraph, i.e. . For the upper bound of the number of simple paths between nodes i and j of the length less than in subgraph the number of all paths (including loops) between these two nodes is calculated as , where is an element of matrix , is an adjacency matrix of subgraph A. For small graphs (n ? 20) and maximal length of paths the number of simple paths between two nodes is insignificantly overestimated.

For the analysis of the approach based on formula (6) and its analogue (7) and (8) exact (with ) has been calculated, the ranks of exact with approximation based on formula (8) with have been compared. The accuracy (rank correlation) of calculations is analyzed with respect to the limitation on the number of paths. The criteria for the considered number of permutations is , where , is an optimal number of permutations.

For subgraphs of size less than 10 nodes formula (7) is considered (without limitations on the number of paths). Figure 6 provides rank correlations of exact and with different parameter L calculated with random permutations (for one of the graphs).

Table 8. Top-10 nodes by and with different number of considered paths.

It can be concluded that the number of considered paths influences the accuracy even if all paths for small subgraphs are considered (i. e. exclusion of some paths can significantly change ranks of nodes). Experimental analysis shows that it is betternot to rely on such approximation due to the fact that it sometimes gives inexact outcome.

As in the previous case this approach is appropriate only for small graphs. This function is applied to graphs with 20 nodes.

The criteria for the accuracy of calculation and maximal path length are similar to the one applied to the previous model. The graph and algorithm characteristics are as follows (information is given for one of the graphs):

Example Network 2:

Table 9. Graph characteristics.

Table 10. Top-5 nodes by Sv and classical centralities.

Table 11. Kendall rank correlation.

Table 12. Spearman rank correlation.

The optimal number of permutation is The number of subgraphs is equal to . The algorithm considers approximately subgraphs.

The third approach is based on the number of edges in a subgraph or, in other words, the number of paths of length 1. In this case thecapacity function looks like

, (8)

· is theindicator function of an edge between two nodes and :

The interpretation of the contribution of a node can be as follows: the bigger the value of a function is the more consolidated a node is. The difference between capacity functions with a node and without this node indicates the number of direct connections of this node. This approach is close to the degree centrality measure but the main difference is that considers different groups of nodes. This approach can be applied to friendshipnetworks where nodes are people and edges are their relationships. High values of detects people that are communicative and active in different communities while the classical degree centrality detects only local central nodes.

For our small example nodes 1, 2, 3, 5 have the same and consequently they have one rank and node 4 has a lower rank.

Due to the fact that this function is not as complicated for the calculation as the other two mentioned above, this function can be applied to graphs of middle size (in this work graphs up to 100 nodes are considered). In total 60 exponentially distributed networks with different number of nodeshave been analyzed. Hence,the complexity of calculations (i. e. the number of required permutations) can be estimated with respect to some graph characteristics. It seems reasonable to study the dependence of the optimal number of permutations on a network density: density includes information about both the number of nodes and the number of edges; a separation of these characteristics is unrepresentative. The criteria for the optimal number of permutations is represented in Table 13:

Table 13. Criteria for

As is seen the higher the density of exponentially distributed graph is the less number of permutation...