Intelligent Data Analytics for Terror Threat Prediction. Группа авторов

Чтение книги онлайн.

СКАЧАТЬ how a rumor can spread over the network.Let’s consider an undirected graph G (V, E), where V is a countable infinite set of nodes, and E is the set of form (i, j) for some i and j in V, and consider the case where initially only one node ν* is the rumor source. For the rumor spreading model, use popular model subject to infected or SI representation which does not permit for any nodes to get well, i.e. once a node with the rumor, it remains such forever. Once a node i with the rumor, it is able to widen it to another node j if and only if there is an edge among them, i.e. if (i, j) ∈ E. A node i needs the time to widen the rumor to node j is modeled by an exponential random variable τij has the rate λ. Suppose there is no loss of generality that λ = 0. All τij’s are autonomous and identically distributed [9].

      2 B. Rumor Source Estimator: Maximum Likelihood (ML)Suppose that the rumor has widen in G (V, E) refer to diffusion model i.e. SI model and all N nodes with the rumor. Infected nodes are symbolized by rumor graph GN (V, E) which is a sub graph of G (V, E). It has been observed that actual rumor source (ν*) may differ than rumor estimator (). By using all these variables ν*, and GN, rumor source estimator is given as follows,(1.3) Where = rumor estimatorν* = rumor source.

      In general trees, evaluation of P (G_N|ν* = ν) is difficult. However in case of regular trees this evaluation is simple because every node has same degree. As the network is tree structure it is possible to spread rumor through unique sequence only. So that finding rumor source is also become simple. Evaluate P (G_N | ν) for all ν ∈ G_N and then select one with maximal value.

      The authors consider general network, random tree, and d-regular tree to find rumor source. For d-regular and random trees it is easy to get information how rumors are diffusing in network as explained earlier but in general network it is difficult. So, they uses Breadth-First-Search (BFS) technique in general networks to convert them into BFS trees. Initially assume every node as a source node which means starting point for BFS. To find origin they used BFS tree with infection probability p. After finding, node which has higher probability considered as source node. For more details see Ref. [9].

      1.6.1.1.2 Snapshot Observation

      This observation gives limited information as discussed earlier in Section 1.5.1.2.2. It is useful for single rumor source detection on social networks, if multiple snapshots are taken in various time intervals. Single snapshot gives limited information about network and states of nodes whereas multiple snapshots give more information about these. Single source detection by applying rumor centrality metric and multiple observations is discussed [37]. They consider tree-like network and used SI model for rumor diffusion, they proves that multiple observations always improve detectable performance. Even two independent snapshot observations increases probability of source detection compare to single snapshot observation. The authors shown that source detection performance increases for multiple observations and decreases with number of infected nodes. After multiple observations use maximum likelihood estimator to find rumor centrality and from it to find rumor source in tree-like network and graph network. Graph network uses BFS technique to transform graph into BFS tree as discussed in above section. The problem in snapshot observation is if SIR model is used for information diffusion, it cannot distinguish between susceptible and recovered nodes.

      1.6.1.1.3 Monitor Observation

      Monitor observation is possible by inserting sensor nodes in network, and monitor these nodes behavior. Sensor nodes placed in network gather information about states of nodes as discussed in Section 1.5.1.2.3. Monitor observation is one of the factors and is useful in identifying source in network. There is chance of missing information about some nodes where sensor nodes are not placed and if number of sensor nodes increases then system performance decreases. But if this observation is considered for source identification, then on collected information use rumor centrality measures to find source of rumor either in tree-like network or general network. In Ref. [49] proposed sensor nodes do not contain any textual information in the network to detect rumor source.

      The above three observations are used to detect RS in social networks.

       1.6.1.2 Query-Based Approach

This approach is proposed in Ref. [18] for source detection. It is purely based on queries and answers to find source. In general, asking queries gives information about rumor source. These queries like “Who shares you the rumor?” or “Are you the source of rumor?” and answers to these queries increases chance of rumor source identification. The authors considers two types of queries: 1) simple batch queries are simple queries as mentioned earlier, and 2) interactive queries are queries which may contain untruth queries and answers with some probability. To quantify the untruthfulness, they propose estimate algorithms for those queries. Author’s uses centrality measures and SI diffusion model and they guarantee that quantifying untruth or truth from these queries and asking these kinds of queries significantly improve performance of source identification in tree-like structure and on Facebook network.

       1.6.1.3 Anti-Rumor-Based Approach

      It is based on anti-rumor diffusion over the network. To broaden antirumor knowledge in the network, monitor based observation is proposed in Ref. [19] for rumor source detection. They injected monitor or sensor nodes to diffuse “anti-rumor” messages inside the network, nodes are called as protectors. Initially, authors prove that injecting anti-rumors decreases performance for Maximum-Likelihood (ML) estimator in largescale networks. If rumors receive anti-rumor find distance between rumor source and protector. To find this distance they propose two algorithms 1) learn distance distributor parameter under ML estimator and 2) Rumor source detector under Maximum-A-Posterior-Estimator (MAPE) based on the learnt parameters. These two learning algorithms give distance between rumor source and protector, based on the difference analyze the actual rumor source.

      1.6.2 Multiple Source Detection

      Many researchers believe that rumor diffusion occurs from only a single source in network, but in general people use several sources to boost the rumor diffusion quickly. Single source identification is comparatively easier and several approaches have already been developed, which are discussed in Section 1.6.1. In this section multiple source of rumor in network is discussed. Detection of multiple sources is proposed in Ref. [48]. They use BFS technique and give final tree after several observations. Following section explains some techniques to find multiple source of rumor. There are four methods: ranking-based, network partitioning, approximation-based and community-based.

In network partitioning rumor centrality is evaluated in two phases [20]. First phase, identify infected nodes and classify into groups, source in each group identified using rumor center method. Second phase, these recognized sources classified into two and in each again uses source estimator to identify source in that group.

      Community-based is proposed in Ref. [21], by partitioning the community to identify several sources in every community. To recognize unseen and improved nodes use reverse diffusion approach through SIR model. Community detection method group all infected nodes into groups. Then apply single source detection approaches to find rumor source in each community. There are two more multiple source detection approaches such as ranking-based and approximation-based. For details see Ref. [10].

1.7 Conclusion

      Social СКАЧАТЬ