Back to results
US 12,585,921 B2Granted
Node selection apparatus and method for maximizing influence using node metadata in network with unknown topology
AssigneeIndustry-Academic Cooperation Foundation, Yonsei University
InventorWon Yong Shin
Life of this patent
Estimating the term…
Abstract
A network node selection apparatus selects a seed node with the greatest influence by expanding the network connection structure by repeating, for a limited number of queries, the process of estimating an edge probability indicating the possibility of the existence of an edge between nodes based on the metadata of a plurality of nodes separately collected in a network where connection information between nodes through the edge is not provided, and expanding the network by selecting a query node according to the estimated edge probability, and selecting a seed node from the expanded network.
Claims18
A network node selection apparatus for selecting a seed node capable of maximizing influence in a network without connection information, comprising:
- memory;
- and
- a processor configured to execute tangible instructions stored in the memory,
- wherein the processor, when executed:
- collects metadata representing all collectible data for each of a plurality of nodes included in the network;
- obtains a final subgraph by repeating, for a predetermined limited number of times, a process of receiving a subgraph including metadata for the plurality of nodes and edges connecting between nodes previously ascertained through a query, creating virtual edges according to all connectable node combinations between nodes except for edges ascertained by the query and connecting nodes with the virtual edges, creating a virtual edge graph by weighting the corresponding virtual edge with an edge probability, which is the probability that an edge exists between nodes of the corresponding combination, obtained by computing the metadata of nodes according to each combination with an artificial neural network, selecting a query node to request a query to a network server from among the nodes of the subgraph based on the virtual edge graph and transmitting the query, and, when edge and node information connected to the selected query node are obtained in response to the transmitted query, combining the obtained edge and node information with the subgraph to obtain an expanded subgraph;
- and
- receives the final subgraph, analyzes an influence of each node in a predetermined way based on a connection relationship in which each of the nodes included in the final subgraph is connected to other nodes through edges, and selects a predetermined number of nodes with high influence as seed nodes,
- wherein the processor obtains the final subgraph by:
- receiving a pre-obtained initial subgraph or a pre-obtained subgraph and metadata for each of the plurality of nodes from the network server, connecting virtual edges between a pair of nodes of all possible combinations in the remaining nodes except for edges connected to the nodes ascertained by the previous query, and generating the virtual edge graph by inferring the edge probability by neural network operation on the metadata and weighting a corresponding virtual edge;
- obtaining an edge pruning graph by removing virtual edges whose edge probability is less than a predetermined reference probability from the virtual edge graph;
- calculating a diffusion probability, which represents a probability that each node will propagate information to other nodes, based on the edge probabilities of edges and virtual edges connected to a plurality of nodes of the edge pruning graph, and obtaining a weighted edge graph by weighting the edges and virtual edges with the calculated diffusion probability as an additional weight;
- selecting a query node for expanding a subgraph from among nodes not selected as a previous query node in a current subgraph based on the weighted edge graph when the number of query transmissions is less than or equal to the limited number;
- and
- transmitting a query to the network server according to the selected query node, receiving a response to the query, and expanding the current subgraph by combining edge and node information included in the received response to the current subgraph.
12 more elements
A network node selection method for selecting a seed node with the greatest influence in a network without connection information, performed by a computer-implemented node selection apparatus comprising a processor and memory configured to execute tangible instructions to improve network operation efficiency, the method comprising the steps of:
- collecting metadata representing all collectible data for each of a plurality of nodes included in the network;
- obtaining a final subgraph by repeating, for a predetermined limited number of times, a process of receiving a subgraph including metadata for the plurality of nodes and edges connecting between nodes previously ascertained through a query, creating virtual edges according to all node combinations that can be connected between nodes except for edges ascertained by query and connecting nodes with the virtual edges, creating a virtual edge graph by weighting the corresponding virtual edge with an edge probability, which is a probability that an edge exists between nodes of the corresponding combination, obtained by performing a neural network operation on the metadata of nodes according to each combination using an artificial neural network, selecting a query node to request a query to a network server from among nodes of the subgraph based on the virtual edge graph and transmitting the query, and, when edge and node information connected to the selected query node are obtained in response to the transmitted query, and combining the obtained edge and node information with the subgraph to obtain an expanded subgraph;
- and
- receiving the final subgraph, analyzing an influence of each node in a predetermined way based on a connection relationship in which each of the nodes included in the final subgraph is connected to other nodes through edges, and selecting a predetermined number of nodes with high influence as seed nodes,
- wherein the step of obtaining the final subgraph further includes the steps of:
- receiving a pre-obtained initial subgraph or a pre-obtained subgraph and metadata for each of the plurality of nodes from the network server, connecting the virtual edge between a pair of nodes of all possible combinations in the remaining nodes except for edges connected to the nodes ascertained by the previous query, and generating the virtual edge graph by inferring the edge probability by neural network operation on the metadata and weighting a corresponding virtual edge;
- obtaining an edge pruning graph by removing virtual edges whose edge probability is less than a predetermined reference probability from the virtual edge graph;
- calculating a diffusion probability, which represents a probability that each node will propagate information to other nodes, based on the edge probabilities of edges and virtual edges connected to a plurality of nodes of the edge pruning graph, and obtaining a weighted edge graph by weighting the edges and virtual edges with the calculated diffusion probability as an additional weight;
- when the number of query transmissions is less than or equal to the limited number, selecting a query node for expanding a subgraph from among nodes not selected as a previous query node in a current subgraph based on the weighted edge graph;
- and
- transmitting a query to the network server according to the selected query node, receiving a response to the query, and expanding the current subgraph by combining edge and node information included in the received response to the current subgraph.
8 more elements
Dependencies are inferred from the claim text.