Method for querying high-connectivity shortest influence path between users, device, and product

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.