Source localization method for rumor based on full-order neighbor coverage strategy

Patent metadata

Field	Value
Publication number	US-12518183-B2
Application number	US-202217970718-A
Country	US
Kind code	B2
Filing date	Oct 21, 2022
Priority date	Oct 21, 2022
Publication date	Jan 6, 2026
Grant date	Jan 6, 2026

Abstract

Source localization method for rumor source based on full-order neighbor coverage strategy includes: constructing a network graph according to the user relationship in the actual target area; mapping an actual relationship into the network graph; determining sensors in the network graph, and deploying users corresponding to the sensors as observation users in an actual target area; executing a source inferring strategy when the number of the observation users in the actual target area who have received the rumor reaches an expected scale; calculating source likelihood score of non-sensor nodes in the network graph corresponding to the non-observation users in the actual target area; processing differentially the source likelihood scores; and outputting the non-observation user corresponding to the minimum source likelihood score as the source.

First claim

What is claimed is:

1 . A source localization method for rumor based on full-order neighbor coverage strategy, comprising:
(S1) inputting a user relationship database in an actual target area requiring sensor deployment and source localization; (S2) constructing and initializing a network graph G=(V,E) based on the actual target area; wherein after the user relationship database is input, an actual relationship is mapped into the network graph G; V is a set of nodes corresponding to users in the actual target area; E is a set of edges, and the connected edges in the network graph G indicate that corresponding two users know each other in the actual target area; and all nodes in the network graph G are initialized to a susceptible state which means the corresponding users in the actual area do not receive a rumor; (S3) deploying observation users in the actual target area according to the network graph G; wherein sensors are selected in the network graph G with a deployment ratio φ using the full-order neighbor coverage strategy; the full-order neighbor coverage strategy is configured to ensure that there are sensors in each order neighbor of any node in the network graph G; and users in the actual target area corresponding to the deployed sensors in the network graph G are marked as the observation users to record time and direction when they receive propagation information of the rumor; (S4) when the number of observation users who have received rumor's propagation information reaches four in the actual target area, performing a source inferring strategy to detect a source of the rumor; (S5) mapping time and direction recorded by the observation users to the network graph G; (S6) locating the source of the rumor by using graph theory with a topological structure of the network graph G; wherein an initial source likelihood score Score′ v of a non-sensor node v in the network graph G corresponding to a non-observation user in the actual target area is calculated through a following formula: wherein Ō is a set of sensors in the network graph G corresponding to the observation users who have received the propagation information of the rumor in the actual target area; |Ō| represents a number of elements in the Ō, and |Ō| is 4; d i,v is a shortest distance between a sensor i and the non-sensor node v in the network graph G; and t i denotes a timestamp at which the sensor i observes the rumor in the network graph G, corresponding to the observation user in the actual target area; (S7) differentially processing source likelihood scores; wherein for any non-sensor node, if there is a first-order neighbors belonging to sensors who has not received the propagation information of the rumor, a source likelihood score of such a non-sensor node is multiplied by a penalty coefficient α to reduce possibility of a corresponding user becoming the source of the rumor; and α is a real number between 1 and 1.1; (S8) traversing all non-sensor nodes, and obtaining nodes with a minimum source likelihood score; and predicting the user in the actual target area related to the nodes with a minimum source likelihood score in the network graph G as an original rumor source in real life.

2 . The source localization method of claim 1 , wherein the step (S3) is performed through steps of:
(S31) selecting initially sensors in the network graph G by using the full-order neighbor coverage strategy to ensure that for each node in the network graph G, there is at least one sensor in each order neighbor from a first-order neighbor to an eccentricity-order neighbor of the node, so as to allow the sensors to be widely deployed in the network graph G; (S32) determining whether a ratio of the sensors selected by using the full-order neighbor coverage strategy to the network graph G reaches the deployment ratio φ; if no, further selecting non-sensor nodes in the network graph G by using other strategies; and selecting more sensors in the network graph G until the deployment ratio φ is reached; and (S33) marking the users who are sensors in the network graph G as the observation users in the actual target area.

3 . The source localization method of claim 2 , wherein in step (S32), the other strategies comprise random selection of sensors and selection of nodes with the highest degree in the network graph G as the sensors.

4 . The source localization method of claim 1 , wherein in the step (S7), the source likelihood score is processed through a following formula:
Score v =Score′ v *Π j=1 j=neighbor(v)∩O\Ō| α;
wherein Score′ v is the initial source likelihood score of the non-sensor node v in the network graph G corresponding to the non-observation user in the actual target area obtained in the step (S6); α is the penalty coefficient configured to increase penalty for nodes in the network graph G corresponding to users in the actual target area who are unlikely to be the source of the rumor, and is equal to 1.05; neighbor(v) is a first-order neighbor of the non-sensor node v in the network graph G; O is a set of the sensors corresponding to the observation users with the deployment ratio φ in the actual target area, and the deployment ratio φ is 20%, 30% or 40%; and Ō is the set of sensors corresponding to the observation users in the actual target area who have received the propagation information of the rumor.

5 . The source localization method of claim 1 , wherein the deployment ratio φ is 20%, 30% or 40%.

6 . The source localization method of claim 1 , wherein the penalty coefficient α is 1.05.

Assignees

• Univ Northwestern Polytechnical

Inventors

• Wang Zhen
• Hou Dongpeng
• Li Xianghua
• Gao Chao

Classifications

• G06Q50/265 Primary

  Personal security, identity or safety · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title

• G06N5/04 Primary

  Inference or reasoning models · CPC title