Granted Patent B1

US 12,645,739 · App. 19/022,055 · Granted Jun 2, 2026

Inventors: Yuxuan Ji (Hangzhou City, CN); Jian Xu (Hangzhou City, CN); Wanning Wan (Hangzhou City, CN)

Assignee: Hangzhou Dianzi University

G06F16/9024G06F16/9536G06Q30/02011G06Q30/02022G06Q10/40

Abstract

Claims (56)

1 . A method for querying a high-connectivity shortest influence path between users, implemented by a computer device comprising a memory, a processor, and a computer program stored in the memory and executable on the processor, wherein the method comprises:

receiving, by the processor, a social network graph, a start node and a target node;

constructing, by the processor, an indexed linked list data structure based the social network graph, wherein the social network graph comprises a plurality of nodes and edges connecting adjacent ones of the nodes, the nodes represent users in a social network, the edges represent mutual influence between adjacent ones of the users, and two nodes connected by each edge are neighboring nodes; the indexed linked list data structure is a linked list array data structure corresponding to each object node, and the linked list array data structure comprises the object node, one or more single-hop connectivities corresponding to the object node, and a neighboring node linked list corresponding to each single-hop connectivity; and the single-hop connectivity is a quantity of common neighboring nodes of adjacent nodes;

determining, by the processor, a path connectivity in a current iteration based on a minimum path connectivity in a previous iteration, and determining, by the processor based on a given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is a shortest influence path satisfying the given path connectivity, wherein the given path connectivity is the path connectivity in the current iteration; and if the current iteration is the first iteration, the minimum path connectivity in the previous iteration is set to 1;

if there is a shortest influence path satisfying the given path connectivity, calculating, by the processor, a shortest influence path in the current iteration and a path connectivity corresponding to the shortest influence path in the current iteration, updating the minimum path connectivity in the previous iteration to the path connectivity corresponding to the shortest influence path in the current iteration, and returning to the step of “determining a path connectivity in a current iteration based on a minimum path connectivity in a previous iteration, and determining, based on a given path connectivity, the indexed linked list data structure, a start node, and a target node, whether there is a shortest influence path satisfying the given path connectivity”; or

if there is no shortest influence path satisfying the given path connectivity, updating, by the processor, a maximum path connectivity in the previous iteration to the path connectivity in the current iteration to obtain a search range of the path connectivity;

continuing, by the processor, the iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration until a high-connectivity shortest influence path is determined; and

propagating information between the users along the high-connectivity shortest influence path.

2 . The method for querying a high-connectivity shortest influence path between users according to claim 1 , wherein continuing, by the processor, the iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration until the high-connectivity shortest influence path is determined comprises:

determining an intermediate path connectivity in the current iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration, updating the path connectivity in the current iteration to the intermediate path connectivity in the current iteration, and determining, based on the given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is a shortest influence path satisfying the given path connectivity, to obtain a first determining result;

if the first determining result is yes, calculating the shortest influence path in the current iteration and the path connectivity corresponding to the shortest influence path in the current iteration, and updating the minimum path connectivity in the previous iteration to the path connectivity corresponding to the shortest influence path in the current iteration; and determining whether a difference between the minimum path connectivity and the maximum path connectivity in the previous iteration is 1, to obtain a second determining result;

if the second determining result is yes, stopping the iteration, and determining the shortest influence path in the current iteration as the high-connectivity shortest influence path; or

if the second determining result is no, returning to the step of “determining an intermediate path connectivity in the current iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration, updating the path connectivity in the current iteration to the intermediate path connectivity in the current iteration, and determining, based on the given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is a shortest influence path satisfying the given path connectivity, to obtain a first determining result”;

if the first determining result is no, updating the maximum path connectivity in the previous iteration to the path connectivity in the current iteration, and determining whether the difference between the minimum path connectivity and the maximum path connectivity in the previous iteration is 1, to obtain a third determining result; and

if the third determining result is yes, stopping the iteration, and determining a shortest influence path in the previous iteration as the high-connectivity shortest influence path; or

if the third determining result is no, returning to the step of “determining an intermediate path connectivity in the current iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration, updating the path connectivity in the current iteration to the intermediate path connectivity in the current iteration, and determining, based on the given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is a shortest influence path satisfying the given path connectivity”.

3 . The method for querying a high-connectivity shortest influence path between users according to claim 2 , wherein determining, by the processor based on the given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is the shortest influence path satisfying the given path connectivity comprises:

creating an initial set and state variables, wherein the initial set comprises the start node in an initial phase, and the state variables comprise a first state variable D(w), a second state variable P(w), and a third state variable CN_P(w); the first state variable D(w) represents a length of a shortest path from the start node to a node w passing through a node v′ in a current phase, the node v′ is a node newly added to the initial set in the current phase, and the node w is a neighboring node of the node v′ and is not added to the initial set in the current phase; the second state variable P(w) represents a predecessor node, and the second state variable P(w) is the node v′; and the third state variable CN_P(w) represents a single-hop connectivity between the node w and the second state variable P(w);

adding the node v′ with a minimum value of the first state variable D(w) in the current phase to the initial set to obtain an updated initial set;

traversing an indexed linked list data structure of the node v′, and determining whether a single-hop connectivity of the node v′ is greater than or equal to the given path connectivity; and

if the single-hop connectivity of the node v′ is greater than or equal to the given path connectivity, obtaining a neighboring node of the node v′ and with a single-hop connectivity greater than or equal to the given path connectivity, and updating the state variables; returning to the step of “adding the node v′ with a minimum value of the first state variable D(w) in the current phase to the initial set”, until all nodes in the social network are in the initial set or the first state variable D(w) of any node that is not in the initial set is ∞; and determining whether the first state variable D(w) of the target node is ∞, and if the first state variable D(w) of the target node is ∞, determining that there is no shortest influence path corresponding to the given path connectivity, or if the first state variable D(w) of the target node is not ∞, determining that there is a shortest influence path corresponding to the given path connectivity; or

if the single-hop connectivity of the node v′ is less than the given path connectivity, determining that there is no shortest influence path corresponding to the given path connectivity.

4 . The method for querying a high-connectivity shortest influence path between users according to claim 1 , wherein in a process of determining the search range of the path connectivity, determining, by the processor, the path connectivity in the current iteration based on the minimum path connectivity in the previous iteration comprises:

determining twice the minimum path connectivity in the previous iteration as a maximum path connectivity in the current iteration.

5 . The method for querying a high-connectivity shortest influence path between users according to claim 3 , wherein the updating the state variables comprises:

updating the first state variable D(w) based on the following formula:

D ( w )=min( D ( w ), D ( v ′)+1)

wherein D(v′) represents a length of a shortest path in a previous phase, and if the first state variable D(w) changes, the second state variable P(w) is set to the node v′, and the third state variable CN_P(w) is set to a single-hop connectivity between the node v′ and the node w; or if the first state variable D(w) does not change, the second state variable P(w) and the third state variable CN_P(w) remain unchanged.

6 . A computer device, comprising a memory, a processor, and a computer program stored in the memory and executable on the processor, wherein the processor executes the computer program to implement operations comprising:

receiving a social network graph, a start node and a target node;

constructing an indexed linked list data structure based on the social network graph, wherein the social network graph comprises a plurality of nodes and edges connecting adjacent ones of the nodes, the nodes represent users in a social network, the edges represent mutual influence between adjacent ones of the users, and two nodes connected by each edge are neighboring nodes: the indexed linked list data structure is a linked list array data structure corresponding to each object node, and the linked list array data structure comprises the object node, one or more single-hop connectivities corresponding to the object node, and a neighboring node linked list corresponding to each single-hop connectivity; and the single-hop connectivity is a quantity of common neighboring nodes of adjacent nodes;

determining a path connectivity in a current iteration based on a minimum path connectivity in a previous iteration, and determining, based on a given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is a shortest influence path satisfying the given path connectivity, wherein the given path connectivity is the path connectivity in the current iteration; and if the current iteration is the first iteration, the minimum path connectivity in the previous iteration is set to 1;

if there is a shortest influence path satisfying the given path connectivity, calculating a shortest influence path in the current iteration and a path connectivity corresponding to the shortest influence path in the current iteration, updating the minimum path connectivity in the previous iteration to the path connectivity corresponding to the shortest influence path in the current iteration, and returning to the step of “determining a path connectivity in a current iteration based on a minimum path connectivity in a previous iteration, and determining, based on a given path connectivity, the indexed linked list data structure, a start node, and a target node, whether there is a shortest influence path satisfying the given path connectivity”; or

if there is no shortest influence path satisfying the given path connectivity, updating a maximum path connectivity in the previous iteration to the path connectivity in the current iteration to obtain a search range of the path connectivity;

continuing the iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration until a high-connectivity shortest influence path is determined; and

propagating information between the users along the high-connectivity shortest influence path.

7 . The computer device according to claim 6 , wherein the continuing the iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration until a high-connectivity shortest influence path is determined comprises:

determining an intermediate path connectivity in the current iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration, updating the path connectivity in the current iteration to the intermediate path connectivity in the current iteration, and determining, based on the given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is a shortest influence path satisfying the given path connectivity, to obtain a first determining result;

if the first determining result is yes, calculating the shortest influence path in the current iteration and the path connectivity corresponding to the shortest influence path in the current iteration, and updating the minimum path connectivity in the previous iteration to the path connectivity corresponding to the shortest influence path in the current iteration; and determining whether a difference between the minimum path connectivity and the maximum path connectivity in the previous iteration is 1, to obtain a second determining result;

if the second determining result is yes, stopping the iteration, and determining the shortest influence path in the current iteration as the high-connectivity shortest influence path; or

if the second determining result is no, returning to the step of “determining an intermediate path connectivity in the current iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration, updating the path connectivity in the current iteration to the intermediate path connectivity in the current iteration, and determining, based on the given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is a shortest influence path satisfying the given path connectivity, to obtain a first determining result”;

if the first determining result is no, updating the maximum path connectivity in the previous iteration to the path connectivity in the current iteration, and determining whether the difference between the minimum path connectivity and the maximum path connectivity in the previous iteration is 1, to obtain a third determining result; and

if the third determining result is yes, stopping the iteration, and determining a shortest influence path in the previous iteration as the high-connectivity shortest influence path; or

if the third determining result is no, returning to the step of “determining an intermediate path connectivity in the current iteration based on the minimum path connectivity and the maximum path connectivity in the previous iteration, updating the path connectivity in the current iteration to the intermediate path connectivity in the current iteration, and determining, based on the given path connectivity, the indexed linked list data structure, the start node, and the target node, whether there is a shortest influence path satisfying the given path connectivity”.

8 . The computer device according to claim 7 , wherein the determining, based on a given path connectivity, the indexed linked list data structure, a start node, and a target node, whether there is a shortest influence path satisfying the given path connectivity comprises:

creating an initial set and state variables, wherein the initial set comprises the start node in an initial phase, and the state variables comprise a first state variable D(w), a second state variable P(w), and a third state variable CN_P(w); the first state variable D(w) represents a length of a shortest path from the start node to a node w passing through a node v′ in a current phase, the node v′ is a node newly added to the initial set in the current phase, and the node w is a neighboring node of the node v′ and is not added to the initial set in the current phase; the second state variable P(w) represents a predecessor node, and the second state variable P(w) is the node v′; and the third state variable CN_P(w) represents a single-hop connectivity between the node w and the second state variable P(w);

adding the node v′ with a minimum value of the first state variable D(w) in the current phase to the initial set to obtain an updated initial set;

traversing an indexed linked list data structure of the node v′, and determining whether a single-hop connectivity of the node v′ is greater than or equal to the given path connectivity; and

if the single-hop connectivity of the node v′ is greater than or equal to the given path connectivity, obtaining a neighboring node of the node v′ and with a single-hop connectivity greater than or equal to the given path connectivity, and updating the state variables; returning to the step of “adding the node v′ with a minimum value of the first state variable D(w) in the current phase to the initial set”, until all nodes in the social network are in the initial set or the first state variable D(w) of any node that is not in the initial set is ∞; and determining whether the first state variable D(w) of the target node is ∞, and if the first state variable D(w) of the target node is ∞, determining that there is no shortest influence path corresponding to the given path connectivity, or if the first state variable D(w) of the target node is not ∞, determining that there is a shortest influence path corresponding to the given path connectivity; or

if the single-hop connectivity of the node v′ is less than the given path connectivity, determining that there is no shortest influence path corresponding to the given path connectivity.

9 . The computer device according to claim 6 , wherein in a process of determining the search range of the path connectivity, the determining a path connectivity in a current iteration based on a minimum path connectivity in a previous iteration comprises:

determining twice the minimum path connectivity in the previous iteration as a maximum path connectivity in the current iteration.

10 . The computer device according to claim 9 , wherein the updating the state variables comprises:

updating the first state variable D(w) based on the following formula:

D ( w )=min( D ( w ), D ( v ′)+1)

wherein D(v′) represents a length of a shortest path in a previous phase, and if the first state variable D(w) changes, the second state variable P(w) is set to the node v′, and the third state variable CN_P(w) is set to a single-hop connectivity between the node v′ and the node w; or if the first state variable D(w) does not change, the second state variable P(w) and the third state variable CN_P(w) remain unchanged.

Assignments (2)

Priority Claims (1)

References Cited (31)