MODEL INDEPENDENT AND NETWORK STRUCTURE DRIVEN RANKING OF NODES FOR LIMITING THE SPREAD OF MISINFORMATION THROUGH LOCATION BASED SOCIAL NETWORKS

A method of limiting misinformation spread through a social network structure using a ranking of nodes of a targeted portion of a social network. Limiting the misinformation spread may be accomplished by: generating a set of permutations of the nodes of the targeted social network; computing a contribution to the spread of influence of each node within the set of randomly generated permutations; determining the average contribution of each of the nodes towards a spread of information within the network; constructing a list of ranked nodes by sorting the nodes in a non-increasing order based on contribution values; and disconnecting at least some of the nodes in order of rank in the list.

BACKGROUND

The present invention relates to ranking of nodes in a network structure, and more specifically to a network structure driven ranking of nodes for limiting the spread of misinformation through location based social networks.

At times negative information (e.g. rumors or viral marketing campaigns), misinformation, or false or inaccurate information (especially that which is deliberately intended to deceive), originates and is spread through a social network. To combat the spread of the negative information or misinformation, specific models are used in prior art systems to aid in preventing the spread of misinformation. Based on the specific models, nodes of the social network are targeted to limit the spread of misinformation. Identifying the nodes to target is difficult.

SUMMARY

According to one embodiment of the present invention, a method of limiting misinformation spread through a social network structure using a ranking of nodes of a targeted portion of a social network is disclosed. The method comprising the steps of: a computer randomly generating a set of permutations of the nodes of the targeted social network; the computer computing a contribution to the spread of influence of each node within the set of randomly generated permutations; the computer, determining the average contribution of each of the nodes towards a spread of information within the network; the computer constructing a list of ranked nodes by sorting the nodes in a non-increasing order based on contribution values; and the computer disconnecting at least some of the nodes in order of rank in the list.

According to another embodiment of the present invention, a computer program product for limiting misinformation spread through a social network structure using a ranking of nodes of a targeted portion of a social network is disclosed. The computer program product comprising a computer comprising at least one processor, one or more memories, one or more computer readable storage media, the computer program product comprising a computer readable storage medium having program instructions embodied therewith. The program instructions executable by the computer to perform a method comprising: randomly generating, by the computer, a set of permutations of the nodes of the targeted social network; computing, by the computer, a contribution to the spread of influence of each node within the set of randomly generated permutations; determining, by the computer, the average contribution of each of the nodes towards a spread of information within the network; constructing, by the computer, a list of ranked nodes by sorting the nodes in a non-increasing order based on contribution values; and disconnecting, by the computer, at least some of the nodes in order of rank in the list.

According to another embodiment of the present invention, a computer system for limiting misinformation spread through a social network structure using a ranking of nodes of a targeted portion of a social network is disclosed. The computer system comprising a computer comprising at least one processor, one or more memories, one or more computer readable storage media having program instructions executable by the computer to perform the program instructions. The program instructions comprising: randomly generating, by the computer, a set of permutations of the nodes of the targeted social network; computing, by the computer, a contribution to the spread of influence of each node within the set of randomly generated permutations; determining, by the computer, the average contribution of each of the nodes towards a spread of information within the network; constructing, by the computer, a list of ranked nodes by sorting the nodes in a non-increasing order based on contribution values; and disconnecting, by the computer, at least some of the nodes in order of rank in the list.

DETAILED DESCRIPTION

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

FIG. 4shows a diagram of identifying and preventing the spread of misinformation in social networks.

A targeted portion of social network comprised of targeted portions of the social network of nodes affected by the misinformation may be filtered102by receiving specifications regarding the misinformation103, input regarding the portions of the user base of the social network which are sensitive towards the misinformation104, and input regarding the geography or location of the user base of the social network105which includes the social network itself.

The social network prior to the filtering may be represented mathematically as G(N, E(N)), wherein G represents “graph”, N represents nodes of the network and E represents edges or connections between the nodes N.

Based on the input received, the nodes of the social network which do not correspond to the input received are removed or filtered out102, leaving a targeted portion of the network109which is provided as input for further ranking106.

The targeted portion of the social network from the filtering102may be represented mathematically as G(N\S, E(N\S)), where G represents “graph”, N represents nodes of the network, E represents edges or connections between the nodes and S represents a subset of nodes, indicating that nodes were removed in the subset along with edges amount the nodes in the subset.

An example of a targeted portion of a social network of nodes is shown inFIG. 3. The targeted portion of the social network is represented by nodes N, where N={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, and preferably includes all of the connections (edges) E between said nodes N. Nodes1-13represent a portion of a much larger network in a geographic location that has N nodes. Misinformation may be found in any of the nodes.

In the example ofFIG. 3, Nodes1,2,3, and5are all interconnected through edges represented by the lines between the nodes. Node4is connected to node3and node5. Node4is connected to node6. Node6is connected to node7. Node8is connected to node9. Node9is connected to node12,13and10. Node11is connected to nodes10,13, and12. Node12is connected to node9,11, and13. Node13is connected to node9,10,11, and12. Node10is connected to9,13and11.

The nodes1-13of the targeted portion of the social network from102are ranked106using a model independent ranking method of the present invention. The model independent ranking106outputs a ranked list of nodes107of a social network which may need to be targeted to slow down (e.g. decrease the speed in which the misinformation is spreading) and/or prevent the spread of misinformation.

The model independent ranking106of the present invention uses ranking mechanisms which take into account a synergy effect. The synergy effect is a level of impact or effect when multiple nodes interact together. To take into account the synergy effect, the model independent ranking106analyzes subsets of nodes, not just the individual nodes. For example, referring toFIG. 3, nodes9and4may be selected as ranking first and second as to the nodes which need to be disconnected to prevent and decrease the speed of misinformation spreading between nodes1,2,3,5to nodes6-13.

The ranked list of nodes107provides Shapley values of the nodes using a sampling-based approach that works in polynomial time. Shapley values are used in this case since the contributions of each node are unequal. As a result, each node gains more value with each connection to other nodes, so that a node with more than one connection has more significance than it would have if it were acting independently.

Based on the ranked list of nodes107, specific nodes may be disconnected108from the social network, decreasing or preventing the misinformation from spreading within the social network at a specific location.

FIG. 5shows a flow diagram of a method of model independent ranking and network structure driven ranking if nodes of limiting the spread of misinformation through location based social networks. Under each discussion of the steps of the method is corresponding pseudocode.

The definition of terms in the following steps can be represented in pseudocode as:Let ´Ω be a set of t randomly sampled permutations.Let Πjbe the j-th permutation in ´Ω.Let R be the number of repetitions.Let Si(Πj) represent the set of nodes that occur before node i in the permutation Πj.Let MC[i] represent the marginal contribution of node i.Let SHirepresent the Shapley value of nodeLet v1and v2represent value functions which assign a value for each subset S of nodes in the network

In a first step (step202), a set ´Ω of permutations of the nodes of the targeted social network are randomly generated by misinformation management function96of the workload layer90cloud computing environment.

The contributions of the sets of nodes in the targeted social network are initialized by the misinformation management function96(step204). Following the order of the nodes dictated by Πi, initially all nodes of the network are inactive and a threshold is randomly assigned to each node. This can be represented in pseudocode as:for i=1 to n doset MC[i]←0end for

A random node, for example node Π1, is activated. The method then determines how many nodes are activated because of the activation of Π1. The determination of how many nodes are activated because of node Π1is the contribution of node Π1. The next node i=2 is considered. If node Π2is already activated due to the activation of node Π1, then the contribution of node Π2is zero. Otherwise, node Π2is activated. The method then determines how many nodes are activated because of the activation of Π2. This becomes the contribution of the node Π2. This process continues up to node Πn.

Then, the contributions of each node to the spread of influence are computed (step206), for example by the misinformation management function96from a graph of the nodes prior to extraction of the targeted portion of the social network102. The spread of influence may be determined by calculating a Shapley value.

Step206is repeated R times using the same starting node Π1. Furthermore, the contribution of the sets of nodes are repeated for each permutation in the set of sampled permutations.

Step206may be represented in pseudocode as follows:

The values of vnin the formula of step206may be calculated in several ways, with n refers to the version used to calculate the contribution of each node to the spread of influences.

In a first embodiment, the model Γ1used to calculate the contribution of each node to the spread of influences is calculated as any subset S of the edges is the inverse of the sum of squares of the cardinalities of the connected nodes after removing the nodes and edges in S from the original given graph G(N, E(N)). In one embodiment v1assigns a value to each subset S of the nodes.

We define the first version of game Γ1=(N, v1) as follows:

For each S⊂N define v1(S) to be:

v1(S)=1∑i∈φ(S)Ci2Where N is the set of nodes in the targeted, social networkWhere S is any subset of N.Where C is the cardinality of iWhere Φ(S)={1, 2, . . . k} is the set of nodes for the k connected nodes in G(N\S, E(N\S))

In an alternate embodiment, the model Γ2used to calculate the contribution of each node to the spread of influences is calculated as the ratio of the number of connected nodes to the sum of cardinalities of the connected nodes after move the nodes in S as well as the edges among the nodes in S from the original given graph G(N, E(N)). In the alternate embodiment v2assigns a value to each subset S of the nodes.

We define the second version of game Γ2=(N, v2) as follows:

For each S⊂N define v2(S) to be:

v2(S)=kC1+C2+⋯+CkWhere N is the set of nodes in the targeted, social networkWhere S is any subset of N.Where C is the cardinality of connected nodesWhere Φ(S)={1, 2, . . . k} is the set of indicesfor the k connected components in G(N\S, E(N\S))

Within the set of sampled permutations, the average contribution of each nodes towards the spread of information is determined by the misinformation management function96of the workload layer90cloud computing environment (step208). The marginal contribution of node i of a randomly sampled set t is then determined.

Step208can be represented in pseudocode as:

for i=1 to n do

end for

The nodes are sorted, for example by their Shapley values, in a non-increasing order of their contribution values and a list of ranked nodes is constructed (step210).

The number of nodes to be disconnected may be determined by the misinformation management function96of the workload layer90cloud computing environment. Given k nodes to be disconnected, as given in the input, the top k nodes in the sorted order are disconnected.

The nodes are disconnected in order of rank (step212) and the method ends.