Graph centrality calculation method and apparatus, and storage medium

Patent metadata

Field	Value
Publication number	US-2019121926-A1
Application number	US-201816227736-A
Country	US
Kind code	A1
Filing date	Dec 20, 2018
Priority date	Oct 27, 2016
Publication date	Apr 25, 2019
Grant date	—

Abstract

A graph centrality determining method includes sampling, at least twice, nodes that are sequentially-connected and connection edges between the nodes, in an original graph representing a network structure, to obtain sampled sub-graphs, determining an influence of each of nodes in the sampled sub-graphs, forming a graph centrality determining result of each of the sampled sub-graphs, based on the influence of each of the nodes in the sampled sub-graphs, determining result of each of the sampled sub-graphs, to the original graph, to obtain an influence of each of the nodes in the original graph, clustering the influence of each of the nodes in the original graph, sorting the influence of each of the nodes in the original graph in descending order of a result of the clustering, and obtaining a predetermined quantity of nodes having influences that are top-ranked, in the original graph.

First claim

What is claimed is:

1 . A graph centrality determining method, the method being performed by at least one processor, and the method comprising:
sampling, at least twice, nodes that are sequentially-connected and connection edges between the nodes, in an original graph representing a network structure, to obtain sampled sub-graphs; determining an influence of each of nodes in the sampled sub-graphs; forming a graph centrality determining result of each of the sampled sub-graphs, based on the influence of each of the nodes in the sampled sub-graphs; mapping the graph centrality determining result of each of the sampled sub-graphs, to the original graph, to obtain an influence of each of the nodes in the original graph; clustering the influence of each of the nodes in the original graph; sorting the influence of each of the nodes in the original graph in descending order of a result of the clustering; and obtaining a predetermined quantity of nodes having influences that are top-ranked, in the original graph.

2 . The method according to claim 1 , wherein the sampling comprises:
performing, by using any node in the original graph as a starting node, a random walk operation in the original graph, by selecting one or more neighboring nodes in the original graph until a termination condition is satisfied; and forming the sampled sub-graphs, based on the one or more neighboring nodes that are selected and connection edges corresponding to the one or more neighboring nodes that are selected, in the original graph.

3 . The method according to claim 1 , further comprising:
traversing connection edges between the nodes in one of the sampled sub-graphs; and based on two vertexes of one of the connection edges being both located in the one of the sampled sub-graphs, adding the one of the connection edges into the one of the sampled sub-graphs.

4 . The method according to claim 1 , wherein the determining the influence of each of the nodes in the sampled sub-graphs comprises:
performing predetermined times of random walk operations for one of the sampled sub-graphs; and allocating a predetermined influence for an accessed node during each of the random walk operations until a quantity of nodes that is accessed during the a respective one of the random walk operations meets a predetermined value.

5 . The method according to claim 4 , wherein the allocating the predetermined influence for the accessed node during each of the random walk operations comprises allocating, for the accessed node, a probability that the accessed node is accessed during the respective one of the random walk operations, as the influence of a respective one of the nodes in the one of the sampled sub-graphs.

6 . The method according to claim 1 , wherein the mapping the graph centrality determining result of each of the sampled sub-graphs, to the original graph comprises:
mapping the influence of each of the nodes in the sampled sub-graphs, respectively to the nodes that are sampled in the original graph; and obtaining at least one influence of the nodes to which the influence of each of the nodes in the sampled sub-graphs is mapped.

7 . The method according to claim 1 , wherein the mapping the graph centrality determining result of each of the sampled sub-graphs, to the original graph comprises:
determining, for the sampled sub-graphs, a sampled node having a connection edge with a non-sampled node, among the nodes that are sampled in the original graph; attenuating the influence of the sampled node that is determined; and determining an influence of the non-sampled node, based on a sum of obtained attenuations.

8 . The method according to claim 1 , further comprising:
calculating average values of the influence of each of the nodes in the original graph; sorting the average values in descending order; and obtaining the predetermined quantity of the nodes having the influences that are top-ranked, in the original graph, as a centrality determining result of the original graph.

9 . The method according to claim 1 , wherein each of the nodes corresponds to a user and the network structure corresponds to a social network, or
each of the nodes corresponds to a station and the network structure corresponds to an urban transport network, or each of the nodes corresponds to a product and the network structure corresponds to an online store.

10 . A graph centrality determining apparatus comprising:
at least one memory configured to store computer program code; and at least one processor configured to access the at least one memory and operate according to the computer program code, the computer program code comprising:
sampling code configured to cause the at least one processor to sample, at least twice, nodes that are sequentially-connected and connection edges between the nodes, in an original graph representing a network structure, to obtain sampled sub-graphs;
determining code configured to cause the at least one processor to:
determine an influence of each of nodes in the sampled sub-graphs; and
form a graph centrality determining result of each of the sampled sub-graphs, based on the influence of each of the nodes in the sampled sub-graphs;

mapping code configured to cause the at least one processor to map the graph centrality determining result of each of the sampled sub-graphs, to the original graph, to obtain an influence of each of the nodes in the original graph; and
clustering code configured to cause the at least one processor to:
cluster the influence of each of the nodes in the original graph;
sort the influence of each of the nodes in the original graph in descending order of a result of the clustering; and
obtain a predetermined quantity of nodes having influences that are top-ranked, in the original graph.

11 . The apparatus according to claim 10 , wherein the sampling code is further configured to cause the at least one processor to:
perform, by using any node in the original graph as a starting node, a random walk operation in the original graph, by selecting one or more neighboring nodes in the original graph until a termination condition is satisfied; and form the sampled sub-graphs, based on the one or more neighboring nodes that are selected and connection edges corresponding to the one or more neighboring nodes that are selected, in the original graph.

12 . The apparatus according to claim 10 , wherein the sampling code is further configured to cause the at least one processor to:
traverse connection edges between the nodes in one of the sampled sub-graphs; and based on two vertexes of one of the connection edges being both located in the one of the sampled sub-graphs, add the one of the connection edges into the one of the sampled sub-graphs.

13 . The apparatus according to claim 10 , wherein the determining code is further configured to cause the at least one processor to:
perform predetermined times of random walk operations for one of the sampled sub-graphs; and allocate a predetermined influence for an accessed node during each of the random walk operations until a quantity of nodes that is accessed during the a respective one of the random walk operations meets a predetermined value.

14 . The apparatus according to claim 13 , wherein the determining code is further configured to cause the at least one processor to allocate, for the accessed node, a probability that the accessed node is accessed during the respective one of the random walk operations, as the influence of a respective one of the nodes in the one of the sampled sub-graphs.

15 . The

Assignees

• Tencent Tech Shenzhen Co Ltd

Inventors

• Wang Rui
• Yin Jun
• Li yong kun
• Chen Wei

Classifications

• G06Q10/40

  Business processes related to social networking or social networking services · CPC title

• G06F30/18 Primary

  Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling (circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18) · CPC title

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title

• G06Q30/0201 Primary

  Market modelling; Market analysis; Collecting market data · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title