Communication condition between entities detection displaying at least partial graphs indicating a location where a detected change occurred

Patent metadata

Field	Value
Publication number	US-9767414-B2
Application number	US-201414263100-A
Country	US
Kind code	B2
Filing date	Apr 28, 2014
Priority date	May 16, 2013
Publication date	Sep 19, 2017
Grant date	Sep 19, 2017

Abstract

A computing unit obtains a graph including nodes and edges and representing a communication condition at first timing and at second timing and detects an edge that is added between the first and second timing among the edges. The computing unit calculates probabilities of transmitting information from each node to nodes coupled to the added edge, selects a subset of the nodes based on the calculated probabilities, selects nodes included in the subset as the starting points of information, calculates first probabilities of transmitting information from the selected nodes to each node based on the graph obtained at the first timing and second probabilities of transmitting information from the selected nodes to each node based on the graph obtained at the second timing, and detects a change in the communication condition between the first and second timing by comparing the first probabilities with the second probabilities.

First claim

What is claimed is:

1. A communication condition change detection method comprising:
obtaining a first data set of a graph representing relationships among information entities at a first timing and a second data set of the graph representing relationships among the information entities at a second timing, the graph including a plurality of nodes representing the information entities that transmit, forward, and receive information and a plurality of edges representing relationships between the plurality of nodes;
detecting an edge that is added between the first timing and the second timing among the edges;
calculating, by a processor, with respect to respective first pairs of first nodes having direct or indirect relationships with second nodes coupled to the added edge and the second nodes, probabilities that information is transmitted from the first nodes to the second nodes and storing the calculated probabilities in association with the respective first pairs in a memory;
selecting a subset of the plurality of nodes based on the calculated probabilities stored in the memory;
selecting nodes included in the subset as starting points of information;
calculating, with respect to respective second pairs of the selected nodes and other nodes having direct or indirect relationships with the selected nodes, first probabilities that information is transmitted from the selected nodes to the other nodes based on the first data set and storing the first probabilities in association with the respective second pairs in the memory;
calculating, with respect to the respective second pairs, second probabilities that information is transmitted from the selected nodes to the other nodes based on the second data set and storing the second probabilities in association with the respective second pairs in the memory;
detecting a change in the relationships between the first timing and the second timing by comparing the first probabilities with the second probabilities stored in the memory; and
displaying, based on the detected change, information of partial graphs of the graph to a display, the partial graphs being separate from each other at the first timing but being connected to each other at the second timing, the information indicating a location where the detected change has occurred in the graph.

2. The communication condition change detection method according to claim 1 , wherein:
the obtaining includes detecting two or more added edges; and
the calculating includes calculating probabilities that information is transmitted from each node to a plurality of nodes each coupled to any of the two or more added edges, and selecting the subset based on a highest probability among the probabilities calculated for each node serving as a starting point.

3. The communication condition change detection method according to claim 1 , wherein:
the obtaining includes detecting two or more added edges; and
the calculating includes extracting an edge included in a subgraph that satisfies a predetermined condition from the two more added edges, and selecting nodes coupled to the extracted edge as end points of information, and calculating the probabilities that information is transmitted from each node.

4. The communication condition change detection method according to claim 3 , wherein the calculating includes calculating, for each node serving as a starting point, a sum of the probabilities that information is transmitted to a plurality of nodes coupled to the extracted edge, and selecting the subset based on the sum.

5. The communication condition change detection method according to claim 3 , wherein the subgraph that satisfies the predetermined condition is a clique having an edge between any two nodes to connect the two nodes.

6. An information processing apparatus for detecting a change of communication condition, the information processing apparatus comprising:
a memory configured to store a first data set of a graph representing relationships among information entities at a first timing and a second data set of the graph representing relationships among the information entities at a second timing, the graph including a plurality of nodes representing the information entities that transmit, forward, and receive information and a plurality of edges representing relationships between the plurality of nodes; and
a processor configured to perform a process including:
detecting an edge that is added between the first timing and the second timing among the edges,
calculating, with respect to respective first pairs of first nodes having direct or indirect relationships with second nodes coupled to the added edge and the second nodes, probabilities that information is transmitted from the first nodes to the second nodes and storing the calculated probabilities in association with the respective first pairs in a memory,
selecting a subset of the plurality of nodes based on the calculated probabilities stored in the memory,
selecting nodes included in the subset as starting points of information,
calculating, with respect to respective second pairs of the selected nodes and other nodes having direct or indirect relationships with the selected nodes, first probabilities that information is transmitted from the selected nodes to the other nodes based on the first data set and storing the first probabilities in association with the respective second pairs in the memory;
calculating, with respect to the respective second pairs, second probabilities that information is transmitted from the selected nodes to the other nodes based on the second data set and storing the second probabilities in association with the respective second pairs in the memory;
detecting a change in the relationships between the first timing and the second timing by comparing the first probabilities with the second probabilities stored in the memory; and
displaying, based on the detected change, information of partial graphs of the graph to a display, the partial graphs being separate from each other at the first timing but being connected to each other at the second timing, the information indicating a location where the detected change has occurred in the graph.

7. A non-transitory computer-readable storage medium storing a computer program that causes a computer to perform a process comprising:
obtaining a first data set of a graph representing relationships among information entities at a first timing and a second data set of the graph representing relationships among the information entities at a second timing, the graph including a plurality of nodes representing the information entities that transmit, forward, and receive information and a plurality of edges representing relationships between the plurality of nodes;
detecting an edge that is added between the first timing and the second timing among the edges;
calculating, with respect to respective first pairs of first nodes having direct or indirect relationships with second nodes coupled to the added edge and the second nodes, probabilities that information is transmitted from the first nodes to the second nodes coupled to the added edge and storing the calculated probabilities in association with the respective first pairs in a memory;
selecting a subset of the plurality of nodes based on the calculated probabilities stored in the memory;
selecting nodes included in the subset as starting points of information;
calculating, with respect to respective second pairs of the selected nodes and other nodes having direct or indirect relationships with the selected nodes, first probabilities that information is transmitted from the selected nodes to the other nodes based on the first data set and storing the first probabilities in association with the respective

Assignees

• Fujitsu Ltd

Inventors

• Maruhashi Koji
• Yugami Nobuhiro

Classifications

• G06N7/01 Primary

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06N7/005 Primary

  Physics · mapped topic