key: cord-026306-mkmrninv
authors: Lepskiy, Alexander; Meshcheryakova, Natalia
title: Belief Functions for the Importance Assessment in Multiplex Networks
date: 2020-05-15
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50143-3_22
sha: 
doc_id: 26306
cord_uid: mkmrninv

We apply Dempster-Shafer theory in order to reveal important elements in undirected weighted networks. We estimate cooperation of each node with different groups of vertices that surround it via construction of belief functions. The obtained intensities of cooperation are further redistributed over all elements of a particular group of nodes that results in pignistic probabilities of node-to-node interactions. Finally, pairwise interactions can be aggregated into the centrality vector that ranks nodes with respect to derived values. We also adapt the proposed model to multiplex networks. In this type of networks nodes can be differently connected with each other on several levels of interaction. Various combination rules help to analyze such systems as a single entity, that has many advantages in the study of complex systems. In particular, Dempster rule takes into account the inconsistency in initial data that has an impact on the final centrality ranking. We also provide a numerical example that illustrates the distinctive features of the proposed model. Additionally, we establish analytical relations between a proposed measure and classical centrality measures for particular graph configurations.

Dempster-Shafer theory of belief functions [1, 2] is a widely used tool to measure belief or conflict between elements in a considered system [1, 2] . Recently it has also found use in the field of social network analysis [3] . Social networks represent interactions that are met between people, countries, in transportation systems, etc.

One of the core problems in network science is the detection of central elements. In [4] a modified evidential centrality and evidential semi-local centrality in weighted network are proposed. The measures use the combination of "high", "low" and "(high, low)" probabilities of the influence based on weighted and unweighted degrees of nodes via Dempster's rule. In [5] the same rule is applied in order to combine different node-to-node interactions in a network. The proposed measures that are able to detect social influencers were applied to Twitter data.

The theory of belief functions can be also adapted to the problem of community detection, i.e. the partition of nodes into tightly connected groups. For instance, in [6] the author proposed a novel method based on local density measures assigned to each node that are further used for the detection density peaks in a graph.

In the frame of the recent work we mostly focus on the problem of the detection of the most influential as well as the most affected elements in networks. The knowledge about the position of nodes plays a significant role in understanding of structural properties of complex systems.

There exist several networking approaches that aim to assess the importance of nodes in graphs. The first class of the methods refers to classical centrality measures [7] . It includes degree centrality measure that prioritizes over nodes with the largest number of neighbors or with the largest sum of incoming/outcoming weights. The eigenvector group of centralities, that includes eigenvector centrality itself, Bonacich, PageRank, Katz, Hubs and Authorities, Alpha centrality, etc., takes into account the importance of neighbors of a node, i.e. the centrality of a vertex depends on centralities of the adjacent nodes [8] [9] [10] [11] [12] . Closeness and betweenness centralities consider the distance between nodes and the number of the shortest paths that go through nodes in a network [13, 14] .

Another class of measures, that detect the most important elements, employs cooperative game theoretical approach. It includes the estimation of Myerson values, that is similar to Shapley-Shubik index calculation [15] . It also requires the introduction of nodes set functions, that can vary depending on the problem statement. In [16] the Hoede-Bakker index is adjusted to the estimation of the influence elements in social networks. In [17] Long-Range Interaction Centrality (LRIC) is proposed, that estimates node-to-node influence with respect to individual attributes of nodes, the possibility of the group influence and indirect interactions through intermediate nodes.

However, all the approaches described above are designed for so-called monoplex networks and require adaptation to complex structures with many types of interactions between adjacent nodes (so-called multilayer networks [18] ). In recent years multilayer networks became one of the central topics in the field of network science. A multilayer network where the set of nodes (or a part of nodes) remains the same through all layers is called multiplex network, which is the object of the research in this work.

There exist several ways for the assessment of central elements in multiplex networks. Firstly, one can calculate centralities for each layer separately and further aggregate the obtained values through all considered networks. Secondly, one can aggregate connections between pairs of nodes to obtain monoplex network and then apply centrality measures to a new weighted graph. The mod-ification of classical centrality measures to interconnected multilayer networks is described in [18, 19] . In [20] social choice theory rules are applied to multiplex networks in order to detect key elements.

However, the final results for these approaches are calculated from the secondary data. In this work we propose a novel technique of the key elements assessment. We construct a mapping between each node and sets of other nodes, which is a mass function. In case of several layers we combine mass functions on each layer to a unique function that can be used for the centrality estimation in the whole system. The key advantages of our approach are that we take into account interactions with different groups of nodes and we are able to estimate node-to-node influence within the whole network structure. We also take into account the consistency on connections on different network layers.

This paper is organized as follows: in Sect. 2 we describe some basic concepts from belief functions theory. In Sect. 3 we propose a centrality measure for onelayer network and apply it to a toy example. In Sect. 4 we develop an approach to elucidate important elements in networks with several layers. In the same Section we apply the proposed method to two-layers network. Section 5 contains a discussion of our approach as well as conclusion to the work.

In this Section we will remind some basic definitions and notions from Dempster-Shafer theory of belief functions [1, 2] that are further employed in this work.

Let X be a finite set that is called frame of discernment and 2 X is a set of all subsets of X. Function m : 2 X → [0; 1] that meets the requirements of normalization condition, i.e. m(∅) = 0 and A∈2 X m(A) = 1, is called basic probability assignment or a mass function. All A ∈ 2 X such that m(A) > 0 are called focal elements and the family of all focal elements is called the body of evidence.

Mass function m can be associated with two set functions namely a belief function denoted by g(A) = B⊂A m(B) and a plausibility function denoted g(A) = B:A∩B =∅ m(B), that is dual to belief function g(A). These two functions can be considered as lower and upper bounds for the probability estimation of event A : g(A) ≤ P (A) ≤ḡ(A), A ∈ 2 X . The value of function g(A) reflects the belief level to the fact that x ∈ A ⊆ X, where x from X. We denote by Bel(X) a set of all belief functions g on set X.

Belief function g can be also represented as a convex combination of categor-

. Note that η X describes vacuous evidence that x ∈ X. Thus, we call this function as vacuous belief function. Additionally, mass function m(A) can be also expressed from belief function g with Möbius transformation as m(A) = B⊂A (−1) |A\B| g (B) .

In this work we mainly focus on combination techniques adopted from Dempster-Shafer theory. By combination we mean some operator R : Bel(X) × Bel(x) → Bel(X) that transforms two belief functions into one belief function. We denote by m = m 1 ⊗ R m 2 the combinations of two mass functions m 1 and m 2 under rule R.

There exist various combination rules that are widely used in the theory and applications of belief functions. For instance, Dempster rule [1] , that is regarded as the pioneered and the most popular combination technique in Dempster-Shafer theory, is calculated as follows:

indicates the level of conflict between two evidences. If K = 1 then the level of conflict is the highest and rule (1) is not applicable in this case. Another combination technique that is similar to Demster rule is Yager combination rule [21] that is defined as

According to this rule, the value of conflict K is reallocated among the mass of ignorance m(X).

Other combination rules are also described in [22] , some generalizations can be found in [23, 24] , axiomatics and the description of conflict rules are reviewed in [25] [26] [27] [28] .

Additionally, discounted technique proposed in [1] can be applied to mass functions in case when various sources of information that are determined by their belief functions have different levels of reliability or different priority. Discounting of mass functions can be performed with the help of parameter α ∈ [0; 1] as follows:

If α = 0 then the source of information is regarded as thoroughly reliable and m α (A) = m(A) ∀A ∈ 2 X . Conversely, if α = 1 then m α (X) = 1 and the related belief function is vacuous.

In this Section we describe a graph model with one layer of interaction as well as the construction of centrality measure based on a mass function for a network.

We consider connected graph as tuple G = (V, E, W ), where V = {v 1 , ..., v n } is a set of nodes, |V | = n, and E = {e(v i , v j )} as a set of edges. For the simplicity, we associate v k with number k, k = 1, ..., n and denote e(v i , v j ) as e ij . In this work we consider undirected network, i.e. e ij ∈ E implies that e ji ∈ E. We also analyze weighted networks, i.e. each edge e ij in network G associates with weight w ij ∈ W . Without loss of generality, we assume that all weights w ij ∈ [0; 1] and w ij = 0 implies that e ij ∈ E. Weight w ij between nodes v i and v j indicates the degree of interaction between corresponding nodes.

Our main focus is to range nodes with respect their importance in a network. We assume that a node is considered to be pivotal if it actively interacts with other nodes in a graph. In our analysis we take into account the connections with distant nodes as well as the cooperation with group of other nodes. More precisely, we suppose that centrality of a node depends on relative aggregated weight of adjacent subgraphs to the considered node. At the same time, the aggregated weight of a subgraph can be estimated with the help of monotonic measures including such measures as belief functions.

We consider a family of belief functions

We denote by |W | = i<j w ij the total sum of all weights in a graph. Next, we define mass function m k of node v k in connected graph G as follows:

where N

is a discount factor that decreases the importance of the connection of node v k with distant nodes. This coefficient can be determined in the following way:

where d is a distance between corresponding nodes. A mass function of the k-th node reaches the higher values on single nodes that are adjacent to the k-th node and the lower values on the pairs of connected nodes that both belongs to the p-neighborhood of node k. Thus, the value of mass function (3) on one-and twoelement sets is proportional to the weights on corresponding edges and inversely proportional to the distance to a considered node. Belief function g k aggregates the obtained mass functions and corresponding weights over all nodes and edges that are contained in p-neighborhood of the k-th node. Other characteristics can be also taken into account as weighted path between nodes, the joint intensity of the connections along the considered path, etc.

It can be seen that the proposed mass function m k : 2 V → [0; 1] satisfies the normalization condition: m k (∅) = 0, A∈2 V m k (A) = 1. Thus, we can regard m k as basic probability assignments and g k = B m k (B)η B are belief functions of V .

Similar measures for the nodes influence assessment in networks are proposed in [29] .

The proposed mass function m k (A) characterizes the distribution of pure interaction of node v k with a set of closely located nodes from A, i.e. we exclude the interactions with other subsets of A in m k (A). The value m k (V ) indicates the level of ignorance of the interactions between node v k and distant nodes in the graph outside N (p) k . The pairwise interaction between nodes can be estimated by the reallocation of m k (A) among all nodes in A. This can be done with the help of so-called pignistic probabilities proposed in [30] :

It has been known that pignistic probabilities for belief function g k = B m k (B)η B defined on V coincide with Shapley values [31] that are widely used in cooperative game theory and are calculated as follows:

Value Bet v k ({u}) indicates the fraction of interaction of node v k with node u.

Hence, the value

shows the total cooperation with node v in graph G. Consequently, the ranking of q values demonstrates the importance on nodes with respect to their activity in the considered graph. We also note that if graph G has several connected components then the proposed analysis is provided for each component separately. The size of each component can be taken into account in order not to overestimate the interactions in small groups.

We illustrate the proposed model on a toy example represented on Fig. 1 . For the graph on Fig. 1 

The same ranking can be obtained with eigenvector centrality measure, which confirms the consistency of the proposed approach.

It can be also proved that if we consider a 1-neighborhood of a node that, in its turn, induces an acyclic subgraph (i.e. a star subgraph) then the centrality value of a node according to formulas (3)-(6) is associated with a degree centrality measure. More precisely, it can be formulated as follows. 

where n(v) = u:e(v,u)∈E w(v, u) is a weighted degree of node v, n = |V |.

According to Proposition 1, the interaction centrality value q v constructed via belief functions is proportional to weighted degree centrality of node v up to the constant term independent of node v with respect to configuration described above.

In many real-world systems the same set of objects can interact with each other in several ways. Thus, an appropriate network model is required in order to qualitatively analyze the relations between nodes. This can be done with the help of a multiplex network that represents a system of graphs with many layers of interaction. The key point here is that the whole system of graphs should be analyzed jointly as a single entity. Next, we describe a multiplex graph model and the technique for the assessment of important elements in such systems.

We consider a multiplex graph as the family of networks G = (V, E (s) , W (s) ) with the common set of nodes V = {v 1 , ..., v n } but distinct set of edges

.., l} indicates a particular network-layer in a multiplex graph with l levels of interaction. As it is stated above, we associate node v k with number k, k = 1, ..., n and denote e (s)

ij . The other notations remain the same adjusted to layer s.

In order to obtain central elements in the whole system we can estimate the important elements at each layer separately, for example, with the help of the approach described above. As the result, we derive a family of vectors q (s) that can be aggregated into a single ranking. However, we consider all layers independently of each other, which means that multiplex system loses its significance. Instead, we consider another approach.

Firstly, we calculate the set of mass functions m for each layer s, s = 1, ..., l. Further, this set can be put together into an aggregated mass function with the help of combination rule R as m k = m

k . Note that discounted coefficients α can be applied at this stage as well. Finally, we can derive centralities for all elements in the considered system as it is described in formulas (5) and (6) .

In order to demonstrate the whole idea let us investigate the following example. Assume that the system of nodes from the graph on Fig. 1 also interacts on another layer as it is shown on Fig. 2 .

The sum of weights for the second graphs is |W | = 4.2. Hence, the belief functions for each node of the graph on Fig. 2 with respect to 2-neighborhood of nodes are following: 

The matrix of pignistic probabilities Bet As the result, centrality vector q (2) is equal to (1.261, 0.762, 0.928, 1.006, 1.045) , that ranks nodes in the following order: v 1 v 5 v 4 v 3 v 2 , that also coincides with eigenvector centrality ranking.

We now bring two graphs together and calculate pairwise aggregation of belief functions g (1) k and g (2) k with the help of Dempster rule D according to formula (1) . As the result, we obtain new belief functions g k = D(g (1) k , g (2) k ) that indicate the interactions between nodes in the multiplex structure. Assuming that discounting parameter α = 0 for both networks we obtain the following belief functions:

Hence, the matrix of pignistic probabilities of aggregated belief functions is If we average over eigenvector centrality values then we obtain the following

, that almost agrees with the ordering of the second graph.

As we can see, the results obtained by two approaches differ significantly. This can be explained by the choice of aggregation rule (1) that takes into account the possible disagreement in initial data. It means that if the connections diverse for some node on different levels of interaction it leads to the decrease of the importance of this node in aggregated ranking. This fact can be seen by the example of node 1 that has only one strong connection in the first graph and three connections in the second graph. Despite the fact that this node is ranked as the first for the second network it has low position in aggregated ranking.

Another important point is that stability through all layers is encouraged by higher ranks. For instance, node 5 is ranked as the first one for both layers separately. However, in aggregated ranking it takes the first place as this node demonstrates more stable connections through both layers as well as node 4.

Additionally, if we consider a 1-neighborhood of nodes in multiplex acyclic graphs with two layers then the following propositions concerning the aggregated interaction centrality value can be proved.

of node v and the Dempster combination rule (1) is used then the aggregated interaction value of node v is equal to (1) , e(u,y)∈E (2) w (1) 

is the level of conflict of node u ∈ V ; B(G) = 1 n u∈V 1

is a constant that is independent of node v.

If we apply Yager combination rule (2) then this expression is simplified.

Proposition 3. If centrality value q v for node v ∈ V in acyclic graph G = (V, E (s) , W (s) ), s = 1, 2, |V | = n, n ≥ 2 is calculated with regard to 1neighborhood N (1) v of node v and the Yager combination rule (2) is used then the aggregated interaction value of node v is equal to

is a constant that is independent of node v.

It can be seen that in the last case the aggregated interaction centrality value of node v is represented as a sum of normalized weighted degree centralities on each layer and the value that represents the interactions of v's neighbors through different layers.

In this work we propose a new approach for the nodes importance assessment in multiplex networks. We apply Dempster-Shafer theory in order to reveal key elements in undirected weighted graphs as well as to aggregate interactions between nodes into the total ranking.

We assess the cooperation of nodes with different subgroups of vertices by evaluating the corresponding belief functions. The proposed model of belief function takes into account the cooperation with nodes and the groups of nodes that are located in a given neighborhood of a considered vertex. Further, the obtained intensities of cooperation with different groups of nodes are redistributed among the participants of these groups that results in node-to-node intensity of cooperation. The obtained values show real interactions between nodes with respect to distant connections, that is already informative and cannot be derived with most of the classical centrality measures. Finally, we aggregate the pairwise interaction into the final centrality vector that gives the ranking of nodes and helps to reveal key elements in a network.

If nodes cooperate with each other on different levels of interactions then we apply a combination rule to mass functions obtained for different layers of a multiplex structure. In particular, Dempster rule takes into account the disagreement in data on different levels of interaction, i.e. it rewards nodes that have consistent connections through all layers and reduces the importance of nodes with unstable links. Additionally, other combination rules can be used as well in order to estimate the aggregated centralities in multilayer networks. These rules may consider the reliability, the inconsistency, the uncertainty, etc. of a network structure in various ways.

It is important to note that the proposed approach can be easily adapted to directed networks. We also emphasize that parameters of the introduced functions such as discounting coefficients, the radius of nodes neighborhood, etc. can be tuned in accordance with the problem statement.

It is also shown that the proposed methods give comparable results for onelayer networks and take into account specifications of a multilayer structure. In further research we aim to improve the proposed approach and apply the developed methods to real networks.

Upper and lower probabilities induced by a multivalued mapping

Mathematical Theory of Evidence

Belief approach for social networks

A modified evidential methodology of identifying influential nodes in weighted networks

A reliability-based approach for influence maximization using the evidence theory

Evidential community detection based on density peaks

Networks: An Introduction

Power and centrality: a family of measures

The anatomy of a large-scale hypertextual Web search engine

A new status index derived from sociometric index

Authoritative sources in a hyperlinked environment

Eigenvector-like measures of centrality for asymmetric relations

Communication patterns in task-oriented groups

A set of measures of centrality based upon betweenness

Graphs and cooperation in games

A model of influence in a social network

Power in network structures

Multilayer networks

Centrality in interconnected multilayer networks

Influence assessment in multiplex networks using social choice rules

On the Dempster-Shafer Framework and New Combination Rules

Combination of evidence in Dempster-Shafer theory

The choice of generalized Dempster-Shafer rules for aggregating belief functions

General schemes of combining rules and the quality characteristics of combining

Toward an axiomatic definition of conflict between belief functions

The application of conflict measure to estimating incoherence of analyst's forecasts about the cost of shares of russian companies

The contradiction between belief functions: its description, measurement, and correction based on generalized credal sets

On the conflict measures agreed with the combining rules

Identifying influential nodes in weighted network based on evidence theory and local structure

The transferable belief model

A value for n-person games

Acknowledgements. The article was prepared within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE University) and supported within the framework of a subsidy by the Russian Academic Excellence Project '5-100'. This work is also supported by the Russian Foundation for Basic Research under grant No 18-01-00877a.