Method and apparatus to identify the source of information or misinformation in large-scale social media networks

A method of identifying an unknown source of information communicated from an associated source node in a social media network, the method comprising:

• identifying a plurality of node clusters from nodes in the network, including the source node, each of the plurality of node clusters including a plurality of nodes, each of the plurality of nodes from each of the plurality of node clusters having at least one edge connection defined by a connection to a different node from a same one of the node clusters;
• identifying a plurality of gateway nodes from each of the plurality of node clusters, each of the plurality of gateway nodes from each of the plurality of node clusters having at least one weak tie connection with a corresponding gateway node from a different one of the plurality of node clusters;
• selecting a subset of the plurality of gateway nodes as sensor nodes;
• measuring arrival times of the information from the source node at each of the sensor nodes;
• selecting a candidate node cluster from the plurality of node clusters based on high betweenness centrality, the candidate node cluster having a high probability of including the source node from among its corresponding plurality of nodes;
• selecting a subset of the plurality of nodes in the candidate cluster as candidate sensor nodes,
• measuring arrival times of the information from the source node at each of the candidate sensor nodes;
• and
• selecting a candidate node from the candidate cluster based on high betweenness centrality, the candidate node having a high probability of being the source node,
• wherein betweenness centrality of a node v is defined as
• BC
• ⁡
• (
• v
• )
• =
• ∑
• s
• ≠
• v
• ≠
• t
• ⁢
• ⁢
• (
• N
• s
• ,
• t
• SP
• ⁡
• (
• v
• )
• /
• N
• s
• ,
• t
• SP
• )
• ,
• where Ns,tSP(v) is the number of shortest paths from s to t passing through node v, and Ns,tSP is the total number of shortest paths from node s to node t;
• and
• wherein the step of selecting based on betweenness centrality includes determining a betweenness centrality order, where the nodes are ranked in descending order of BC values, and the node with the highest BC value is given a betweenness centrality score (“BCS”) of 1, the varying weights between the nodes implying varying connectivity and the expected BCS for each node vϵVgate is approximated using the m most likely graphs as
• BCS
• ⁡
• (
• v
• )
• _
• =
• ∑
• j
• =
• 1
• m
• ⁢
• ⁢
• Pr
• ⁡
• (
• G
• j
• gate
• )
• ⁢
• BCS
• j
• gate
• ⁡
• (
• v
• )
• ,
• where BCSjgate(v) is the BCS for the vth node in the ith possible graph Gigate, the computational complexity is O(m·|Egate|·|Vgate|), where |Egate| and |Vgate| denote the number of edges and nodes in the graph Gigate, respectively.