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

Cross-reference to related application

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2013-103820, filed on May 16, 2013, the entire contents of which are incorporated herein by reference.

Field

The embodiments discussed herein are related to a communication condition change detection method and a communication condition change detection apparatus.

Background

Today, users use various types of client apparatuses (for example, computers, mobile terminals, and so on). By operating such client apparatuses, the users are able to access a server apparatus on a network, and use services provided by the server apparatus. For example, there is a service called a social network service (SNS). The SNS connects multiple users through a network, and helps the users to interact with each other.

On SNS, users transmit information to other already connected users by operating their client apparatuses. For example, a first user transmits information indicating that the first user likes certain content on a Web page to a server apparatus from his client apparatus. Then, the server apparatus transmits information indicating that the first user likes the content to a second user who is connected to the first user. If the second user who has received the information also likes the content, the second user may transmit such information to a third user in the same way. Thus, the information may be transmitted to users who are not directly connected to the first user who originated the information. The users are able to increase the number of recipients of information by making more connections with other users.

Meanwhile, there has been proposed a method of analyzing communication of information based on connections between users on SNS. For example, connections between users may be represented by a graph in which users are represented as nodes and connections between the users are represented as edges (lines connecting the nodes). By performing predetermined operations using an adjacency matrix representing such a graph, an indicator called Random Walk with Restart (RWR) is calculated. The RWR is an indicator representing the probability that, when information is transmitted from a starting node through a random path along the edges, the information reaches an end node of interest. For example, there has been proposed a method of tracking changes in the RWRs between the nodes specified by the user, in the case where edges are added as time passes. This method performs a fast update of data used for approximate calculation of the RWRs between the specified nodes, only for a small number of added edges.

Examples of the related art are disclosed in:

Jia-Yu Pan et al, “Automatic Multimedia Cross-modal Correlation Discovery”, Proceedings of SIGKDD 2004, ACM SIGKDD, 2004; and

Hanghang Tong et al., “Proximity Tracking on Time-Evolving Bipartite Graphs”, Proceedings of SDM2008, SIAM, 2008, p. 704-715.

New connections are made between information entities (for example, users) as time passes. This is represented as addition of edges between the nodes in a graph. For example, when an edge is added between first and second nodes representing first and second information entities, this indicates that direct communication between the first and second information entities is enabled. If the second information entity has an existing connection to a third information entity, information originated from the first information entity is more likely to be transmitted to the third information entity and other information entities therearound through the second information entity. That is, addition of a small number of edges may significantly increase the communication range which has been only locally established.

Summary

According to one aspect of the invention, there is provided a communication condition change detection method that includes: obtaining a graph representing a communication condition at a first timing and at a second timing, the graph including a plurality of nodes representing information entities that transmit, forward, and receive information and a plurality of edges representing communication 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, probabilities that information is transmitted from each node to nodes coupled to the added edge; selecting a subset of the plurality of nodes based on the calculated probabilities; selecting nodes included in the subset as starting points of information; calculating first probabilities that information is transmitted from the selected nodes to each node based on the graph obtained at the first timing and second probabilities that information is transmitted from the selected nodes to each node based on the graph obtained at the second timing; and detecting a change in the communication condition between the first timing and the second timing by comparing the first probabilities with the second probabilities.

The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims.

It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention.

Brief description of drawings

FIG. 1 illustrates a communication condition change detection apparatus according to a first embodiment;

FIG. 2 illustrates an exemplary hardware configuration of the communication condition change detection apparatus according to the first embodiment;

FIG. 3 illustrates an information processing system according to a second embodiment;

FIG. 4 illustrates an example of the entire graph according to the second embodiment;

FIG. 5 illustrates an example of communication of information according to the second embodiment;

FIG. 6 illustrates an exemplary hardware configuration of a server according to the second embodiment;

FIG. 7 illustrates an exemplary functional configuration of the server according to the second embodiment;

FIG. 8 illustrates an example of a part of a graph according to the second embodiment;

FIG. 9 illustrates examples of adjacency matrices according to the second embodiment;

FIG. 10 is a flowchart of change detection according to the second embodiment;

FIG. 11 illustrates a first example of RWRs at time t−1 according to the second embodiment;

FIG. 12 illustrates a second example of RWRs at time t−1 according to the second embodiment;

FIG. 13 illustrates an example of RWRs at time t according to the second embodiment;

FIG. 14 illustrates an example of a location where a change is detected according to the second embodiment;

FIG. 15 illustrates an example of change detection according to the second embodiment;

FIG. 16 illustrates examples of added cliques according to a third embodiment;

FIG. 17 is a flowchart of change detection according to the third embodiment;

FIG. 18 illustrates an example of RWRs at time t−1 according to the third embodiment;

FIG. 19 is a flowchart of change detection according to a fourth embodiment; and

FIG. 20 illustrates an example of RWRs at time t−1 according to the fourth embodiment.

Description of embodiments

Changes in communication conditions may be the subject of analysis. For example, if an active communication is detected between two groups having preferences in different product areas, this information may be used for marketing purposes. Further, if an active discussion is detected between research groups of different technical fields, this information may be used for analyzing changes in technical trends. For making an analysis, for example, changes in the condition of communications from all nodes to all nodes may be calculated so as to determine the locations where changes have occurred. However, there exist a number of connections between information entities, and a huge number of nodes and edges may be contained in a graph to be analyzed. Therefore, if changes in the condition of communications from all nodes to all nodes are calculated, the calculation cost might be increased.

Several embodiments will be described below with reference to the accompanying drawings, wherein like reference numerals refer to like elements throughout.

(a) First Embodiment

FIG. 1 illustrates a communication condition change detection apparatus 1 according to a first embodiment. The communication condition change detection apparatus 1 detects a change in the condition of communications between information entities that are capable of transmitting, forwarding, and receiving information. The information entity may be a person or a machine. If the information entity is a machine, the information entity may be an information processing apparatus such as computer and the like, or an electronic apparatus such as mobile phone, mobile terminal, and the like.

The communication condition change detection apparatus 1 includes a storage unit 1 a and a computing unit 1 b . The storage unit 1 a may be a volatile storage device such as random access memory (RAM) and the like, or may be a non-volatile storage device such as hard disk drive (HDD), flash memory, and the like. The computing unit 1 b may include a central processing unit (CPU), a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), and the like. The computing unit 1 b may be a processor that performs a program. The term “processor” as used herein refers to a set of plurality of processors (multiprocessor) as well as a single processor.

The storage unit 1 a stores graphs 2 and 3 each containing a plurality of nodes representing information entities and a plurality of edges representing communication between the plurality of nodes. The graph 2 (first graph) represents the communication condition at a first timing. The graph 3 (second graph) represents the communication condition at a second timing. For example, the second timing is timing after the first timing.

For example, the graph 3 contains nodes Na, Nb, Nc, Nd, Ne, and Nf and edges E 1 , E 2 , E 3 , and E 4 . The edge E 1 represents communication between the nodes Na and Nd. The edge E 2 represents communication between the nodes Nb and Ne. The edge E 3 represents communication between the nodes Nc and Ne. The edge E 4 represents communication between the nodes Nc and Nf.

The computing unit 1 b detects edges added between the first timing and the second timing, based on the graphs 2 and 3 . For example, the graph 2 does not contain any of the edges E 1 , E 2 , E 3 , and E 4 . In this case, the computing unit 1 b detects the added edges E 1 , E 2 , E 3 , and E 4 by comparing the edges contained in the graphs 2 with the edges contained in the graph 3 . The computing unit 1 b may detect two or more added edges.

The computing unit 1 b calculates probabilities that information is transmitted from each node (starting node) to nodes (end nodes) connected to any of the added edges. In the case of the graph 3 , nodes that are connected to any of the added edges E 1 , E 2 , E 3 , and E 4 are the nodes Na, Nb, Nc, Nd, Ne, and Nf. For example, the computing unit 1 b calculates RWRs from each node to the nodes Na, Nb, Nc, Nd, Ne, and Nf, based on the graph 2 . The RWRs are indicators of the probabilities that information is transmitted from each starting node to each of the end nodes Na, Nb, Nc, Nd, Ne, and Nf.

The computing unit 1 b selects a subset G of a plurality of nodes, based on the calculated probabilities. For example, the computing unit 1 b may select the subset G based on the highest probability among the probabilities calculated for each starting node. For instance, the computing unit 1 b may select nodes whose highest probability is greater than a predetermined threshold as elements of the subset G.

The computing unit 1 b selects nodes contained in the subset G as the starting points of information, and calculates first probabilities that information is transmitted to each node based on the graph 2 , and second probabilities that information is transmitted to each node based on the graph 3 . The computing unit 1 b detects a change in the communication condition between the first and second timings by comparing the first probabilities with the second probabilities.

For example, the computing unit 1 b calculates, as first probabilities, RWRs from the nodes contained in the subset G to each node, based on the graph 2 . Further, for example, the computing unit 1 b calculates, as second probabilities, RWRs from the nodes contained in the subset G to each node, based on the graph 3 . Then, for instance, the computing unit 1 b may detect an edge where the difference between the first and second probabilities is relatively large as a location where there is a change in the communication condition. In a graph 4 , edges where a relatively large change is detected in the graph 3 are indicated by thicker lines than the other edges.

According to the communication condition change detection apparatus 1 , the computing unit 1 b detects the edges E 1 , E 2 , E 3 , and E 4 that are added between the first timing and the second timing, based on the graphs 2 and 3 . The computing unit 1 b calculates the probabilities that information is transmitted from each node to the nodes Na, Nb, Nc, Nd, Ne, and Nf connected to any of the edges E 1 , E 2 , E 3 , and E 4 , and selects the subset G of a plurality of nodes based on the calculated probabilities. The computing unit 1 b selects only the nodes contained in the subset G as the starting points of information, and calculates first probabilities that information is transmitted to each node based on the graph 2 , and second probabilities that information is transmitted to each node based on the graph 3 . The computing unit 1 b detects a change in the communication condition between the first and second timings by comparing the first probabilities with the second probabilities.

Thus, it is possible to efficiently detect a location where there is a relatively large change in the communication condition due to addition of edges. For making an analysis, it might be an option to calculate RWRs by performing predetermined matrix operations on the entire graphs obtained at different timings, and compare the calculated RWRs, for example. However, the graph might contain a huge number of nodes. Therefore, in the case of performing operations on the entire graph, the memory usage might be increased, resulting in memory shortage. Further, the amount of computation might be increased as well.

In the case where information is transmitted from a first node to a second node, as the number of hops between the first and second nodes decreases (as the number of nodes through which information is transmitted decreases), the probability that information is transmitted increases. Further, as the number of redundant paths between the first and second nodes increases, the probability that information is transmitted increases. On the other hand, as the number of hops between the first and second nodes increases, the probability that information is transmitted decreases. Further, as the number of redundant paths between the first and second nodes decreases, the probability that information is transmitted decreases. That is, if a node has a smaller number of hops to the opposite ends of the added edge and has a greater number of redundant paths to the opposite ends of the added edge, its communication range is more likely to be relatively greatly increased due to addition of edges. On the other hand, if a node has a greater number of hops to the opposite ends of the added edge and has a smaller number of redundant paths to the opposite ends of the added edge, its communication range is less likely to be greatly increased due to addition of edges.

Further, in the case of performing operations on the entire graph, the operations are performed on even the nodes whose communication range is less likely to be greatly increased by addition of edges, which might result in wasteful memory usage and computation. For example, if probabilities that information is transmitted between all the nodes are calculated, the size of memory needed to store the results might be large. More specifically, in the case where the size of memory needed to store the calculation result of each node is 8 bytes and the number of nodes in the graph is 100 million, the size of memory needed to store all the results is as large as 80 petabytes.

In view of the above, the communication condition change detection apparatus 1 calculates probabilities that information is transmitted from each node to the nodes connected to the added edge, and selects the subset G based on the calculated probabilities. Then, the communication condition change detection apparatus 1 selects only the nodes contained in the subset G as the starting points of information, and calculates first and second probabilities that information is transmitted to each node.

In this way, recalculation of the information transmission probability is not performed for nodes whose communication range is less likely to be greatly increased by addition of edges. Accordingly, it is possible to reduce memory usage and the amount of computation, compared to the case where operations are performed on the entire first and second graphs. Further, it is possible to reduce wasteful memory usage and computation. Thus, it is possible to efficiently detect a location where there is a relatively large change in the communication condition due to addition of edges.

Note that the computing unit 1 b may extract an edge contained in a subgraph that satisfies a predetermined condition from two or more added edges, select only the nodes connected to the extracted edge as the end points of information, and calculate the probabilities that information is transmitted from each node. Then, the computing unit 1 b may select the subset G based on the calculated probabilities.

For example, the predetermined condition may be a condition that “a subgraph contains n (n is an integer equal to or greater than 3) or more nodes”. If n=3, a subgraph formed with the nodes Na and Nd and the edge E 1 does not satisfy the condition, and therefore is excluded from the subject of the probability calculation. On the other hand, a subgraph formed with the nodes Nb, Nc, Ne, and Nf and the edges E 2 , E 3 , and E 4 satisfies the condition, and therefore is selected as the subject of the probability calculation. Thus, added edges contained in a subgraph having a predetermined size are selected from among all the added edges. Accordingly, in the case of detecting a change involving a node set having a predetermined size or greater, it is possible to improve the efficiency of computation.

A subgraph may be a clique or a pseudo clique. A clique is a subgraph in which there exist edges connecting each node in the subgraph to all the other nodes in the subgraph. A pseudo clique is a subgraph in which the ratio of edges connecting each node in the subgraph to the other nodes is equal to or greater than a predetermined threshold. In other words, cliques and pseudo cliques are subgraphs in which a plurality of nodes are densely connected. That is, changes in the communication condition due to addition of edges are likely to be greater in cliques and pseudo cliques than in other subgraphs. Therefore, it is possible to efficiently detect relatively large changes by selecting, as candidate elements of the subset G, nodes which are more likely to transmit information to cliques and pseudo cliques.

Further, the computing unit 1 b may calculate, for each starting node, the sum of the probabilities that information is transmitted to a plurality of nodes connected to the edge contained in the subgraph that satisfies the predetermined condition, and select the subset G based on the sum. Thus, for example, it is possible to select only the starting nodes which are more likely to transmit information to the nodes contained in the subgraph. By narrowing down the elements of the subset G, it becomes possible to further reduce the memory usage and the amount of computation when calculating first and second probabilities in the subsequent steps.

FIG. 2 illustrates an exemplary hardware configuration of the communication condition change detection apparatus 1 according to the first embodiment. The communication condition change detection apparatus 1 includes a processor 1 c , a RAM 1 d , an HDD 1 e , a communication unit 1 f , an image signal processing unit 1 g , an input signal processing unit 1 h , a disk drive 1 i , and a device connection unit 1 j . Each unit is connected to a bus of the communication condition change detection apparatus 1 .

The processor 1 c controls information processing performed by the communication condition change detection apparatus 1 . The processor 1 c may be a multiprocessor. Examples of the processor 1 c include a CPU, a DSP, an ASIC, an FPGA, a micro processing unit (MPU), a programmable logic device (PLD), and the like. The processor 1 c may be a combination of two or more of the CPU, DSP, ASIC, FPGA, MPU, and PLD.

The RAM 1 d is a primary storage device of the communication condition change detection apparatus 1 . The RAM 1 d temporarily stores at least part of the operating system (OS) program and application programs that are executed by the processor 1 c . The RAM 1 d also stores various types of data used in processing performed by the processor 1 c.

The HDD 1 e is a secondary storage device of the communication condition change detection apparatus 1 . The HDD 1 e magnetically writes data to and reads data from an internal magnetic disk. The HDD 1 e stores the OS program, application programs, and various types of data. The communication condition change detection apparatus 1 may include other types of secondary storage devices such as a flash memory, a solid state drive (SSD), and the like, and may include a plurality of secondary storage devices.

The communication unit 1 f is an interface capable of communicating with other computers via a network 5 . The communication unit 1 f may be a wired interface or a wireless interface.

The image signal processing unit 1 g outputs an image to a display 5 a connected to the communication condition change detection apparatus 1 , in accordance with an instruction from the processor 1 c . Examples of the display 5 a include a cathode ray tube (CRT) display, a liquid crystal display, and the like.

The input signal processing unit 1 h obtains an input signal from an input device 5 b connected to the communication condition change detection apparatus 1 , and outputs the input signal to the processor 1 c . Examples of the input device 5 b include pointing devices (such as a mouse, a touch panel, and the like), a keyboard, and the like.

The disk drive 1 i is a drive unit that reads programs and data from an optical disc 5 c by using laser beams or the like. Examples of the optical disc 5 c include a digital versatile disc (DVD), a DVD-RAM, a compact disc read only memory (CD-ROM), a CD-Recordable (CD-R), a CD-Rewritable (CD-RW), and the like. The disc drive 1 i reads the programs and data from the optical disc 5 c , and stores the read programs and data in the RAM 1 d or the HDD 1 e , in accordance with an instruction from the processor 1 c , for example.

The device connection unit 1 j is a communication interface that connects peripheral devices to the communication condition change detection apparatus 1 . For example, a memory device 5 d and a reader and writer device 5 e may be connected to the device connection unit 1 j . The memory device 5 d is a recording medium having a function for communicating with the device connection unit 1 j . The reader and writer device 5 e writes data to and reads data from a memory card 5 f . The memory card 5 f is a card-type recording medium. The device connection unit 1 j reads programs and data from the memory device 5 d or the memory card 5 f , and stores the read programs and data in the RAM 1 d or the HDD 1 e , in accordance with an instruction from the processor 1 c , for example.

With this hardware configuration, the communication condition change detection apparatus 1 is realized.

(b) Second Embodiment

FIG. 3 illustrates an information processing system according to a second embodiment. The information processing system of the second embodiment includes a server 100 , personal computers (PCs) 200 and 300 , a mobile phone 400 , and a tablet device 500 . The server 100 , the PCs 200 and 300 , the mobile phone 400 , and the tablet device 500 are connected to a network 10 . The network 10 is the Internet, for example. The network 10 and these apparatuses may be connected through wires or wirelessly. Further, another network may be interposed between the network 10 and these apparatuses. Other than those illustrated in FIG. 3 , various clients used by many users may be connected to the network 10 .

The apparatuses that are used by the users, such as the PCs 200 and 300 , the mobile phone 400 , the tablet device 500 , and the like, may be collectively referred to as “clients” or “client apparatuses”. The users may use an SNS provided by the server 100 or another server connected to the network 10 by operating their clients.

The server 100 is a server computer that analyzes connections between users of the SNS. The server 100 performs analysis based on a graph representing connections between users. The SNS manages friendships between the users. For example, information indicating users who are friends of a user is stored in user management information. The server 100 may generate an analytical graph by referring to the management information. Alternatively, the server 100 may obtain an analytical graph from the other server storing the management information and providing the SNS.

The PC 200 is a client computer used by a user 20 . The PC 300 is a client computer used by a user 30 . The mobile phone 400 is an electronic device used by a user 40 . The tablet device 500 is an electronic device used by a user 50 . For example, the users 20 , 30 , 40 , and 50 may use the SNS by using predetermined software or a Web browser executed by their clients.

For example, connections (friendships) between the users 20 , 30 , 40 , and 50 are represented by a graph in which nodes represent the users 20 , 30 , 40 , and 50 and edges represent connections. As the number of users of the SNS increases, the number of nodes increases, and the number of edges representing connections between users increases.

FIG. 4 illustrates an example of the entire graph according to the second embodiment. A universal set V contains all the nodes using the SNS. Each node corresponds to a single user. If a user is a friend of another user, two nodes representing the two users are connected by an edge. In this way, connections between users of the SNS are represented by an undirected graph. In the graph, nodes are represented by circles (for example, nodes N). Further, edges are represented by lines (for example, edges E). Edges may also be referred to as “links”.

The universal set V contains subgroups V 1 , V 2 , and V 3 . The subgroups V 1 , V 2 , and V 3 are sets of nodes that are relatively densely arranged. For example, when a new connection is made between users of different subgroups, a new edge may be created between the subgroups. Then, communication between the subgroups is enabled through the edge. Each subgroup may contain a user or a group of users who are influential in communication of information (for example, a key person who has many friends and who collects information from a number of other users and distributes the collected information to a number of other users). For example, if influential users or influential groups become friends, the condition of communications between the subgroups may be greatly changed.

Such a relationship is observed in services other than SNS. For example, the subgroups V 1 , V 2 , and V 3 may be groups that are divided according to a certain attribute, such as hobbies, jobs, fields of research and other activities, areas of concern and interest, the place of residence, year of birth, and so on.

For example, a joint authorship of paper may be represented by a graph. More specifically, the subgroup V 1 may be a group of researchers in the field of biology; the subgroup V 2 may be a group of researchers in the field of information sciences; and the subgroup V 3 may be a group of researchers in the field of chemistry. For instance, if the systems biology becomes an increasingly active research area, a prominent researcher in the field of biology (subgroup V 1 ) and a prominent researcher in the field of information sciences (subgroup V 2 ) may jointly write a paper. Then, the condition of communications between the two fields (such as exchanging related papers between the two fields, and so on) may be greatly changed by many biologists and information scientists. Accordingly, although an SNS is described below as an example, the second embodiment may be applied to various types of services (for example, services for collecting and providing academic papers and the like) other than SNS.

FIG. 5 illustrates an example of communication of information according to the second embodiment. FIG. 5 illustrates nodes n 1 , n 2 , n 3 , n 4 , n 5 , n 6 , n 7 , and n 8 , which are part of the universal set V. The nodes n 1 and n 2 are connected by an edge. In other words, the nodes n 1 and n 2 are connected to the opposite ends of the edge. Similarly, the nodes n 1 and n 4 are connected by an edge. The nodes n 2 and n 3 are connected by an edge. The nodes n 3 and n 4 are connected by an edge. The nodes n 3 and n 6 are connected by an edge. The nodes n 3 and n 7 are connected by an edge. The nodes n 4 and n 5 are connected by an edge. The nodes n 3 and n 6 are connected by an edge. The nodes n 5 and n 6 are connected by an edge. The nodes n 6 and n 8 are connected by an edge. The nodes n 7 and n 8 are connected by an edge. Nodes connected to the opposite ends of the same edge have an adjacency relationship. For example, the node n 1 is an adjacent node of the nodes n 2 and N 4 .

As the number of hops (that is, the number of friends needed for transmission) from a first user to a second user decreases, the probability that information is transmitted from the first user to the second user increases. Further, as the number of redundant paths from the first user to the second user increases, the probability that information is transmitted from the first user to the second user increases. Thus, an indicator called an RWR or an RWR distance may be used as an indicator for representing the closeness between nodes which is proportional to the probability that information is transmitted. More specifically, the probability that information generated in a first node is transmitted randomly along the edges to a second node is an RWR distance from the first node to the second node. As the number of hops between the first and second nodes decreases, the RWR distance increases, and information is more likely to be transmitted between the two nodes.

Transmission of information is modeled in the following way. Information is transmitted in accordance with the transition probability between nodes. More specifically, there are the following cases

through (3).

The obtained information is transmitted to at least one adjacent node with a probability of c (c is a real number satisfying 0<c<1).

The obtained information is not transmitted to any of the adjacent nodes with a probability of 1−c. On the model, the information is retransmitted from the source node (the starting node which originated the information).

In the case where a node is adjacent to a plurality of nodes, the probabilities that information is transmitted to the respective adjacent nodes are equal. The probability c may vary depending on the service under analysis. In the second embodiment, c=0.8, for example.

For instance, assuming that information originated from the node n 1 has reached the node n 3 , the probability that the information is transmitted from the node n 3 to each adjacent node is as follows. The probabilities that the information is transmitted from the node n 3 to the respective nodes n 2 , n 4 , n 6 , and n 7 are c/4. The probability that the information is not transmitted from the node n 3 to any of the nodes n 2 , n 4 , n 6 , and n 7 (the probability that the information is retransmitted from the node n 1 ) is 1−c.

The number of all the nodes of the universal set V is N (N is an integer greater than 1). The RWR distances from a node j (“j” is an identifier of the starting node) to all the nodes are held in a column vector r.sub.j with N rows. The column vector r.sub.j is expressed by the following equation (1): r .sub.j= cWr .sub.j+(1− c ) e .sub.j

A matrix W is a transition probability matrix of N rows by N columns. A vector e.sub.j is a column vector whose entry corresponding to the node j is 1 and the other entries are 0. The matrix W is expressed by the following equation

using an adjacency matrix M representing a graph and a diagonal matrix D having the degrees (the number of edges connected to each node) as the diagonal entries. The adjacency matrix M is a matrix in which, if there is an edge between nodes i and j (“i” is an identifier of a node), the elements of the i-th row and j-th column and the j-th row and i-th column are “1”. The other elements of the adjacency matrix M are “0”. W=MD.sup.−1

The following equation

is obtained by solving the equation

for r.sub.j. r .sub.j=(1− c )( I−cW ).sup.−1 e .sub.j

A matrix I is an identity matrix of N rows by N columns. It is possible to calculate RWR distances r.sub.j from the node j to the other nodes using the equation (3).

The method of detecting a relatively large change in the RWR distance is expressed as follows. An RWR distance from xεV to yεV at time t is represented as d(x, y, t). Node sets X⊂V and Y⊂V are a pair of node sets (varying node set pair) in which the ratio of node pairs satisfying d(x, y, t)−d(x, y, t−1)>α (α is a positive real number) to all the node pairs (x, y)ε{X×Y} is β (β is a positive real number) or greater. Then, a varying node set pair in which the number of node pairs (the number of nodes of X×the number of nodes of Y) is γ (γ is a positive integer) or greater is detected from among a plurality of varying node set pairs, and information indicating the detected varying node set pair is provided. However, it is inefficient to calculate d(x, y, t) for all the node pairs (x, y)εV. This is because nodes around the added edge are more likely to relatively greatly contribute to a change in the RWR distance. Thus, before calculating RWR distances, the server 100 narrows down the node pairs on which operations are to be performed.

FIG. 6 illustrates an exemplary hardware configuration of the server according to the second embodiment. The server 100 includes a processor 101 , a RAM 102 , an HDD 103 , a communication unit 104 , an image signal processing unit 105 , an input signal processing unit 106 , a disc drive 107 , and a device connection unit 108 . Each unit is connected to a bus of the server 100 .

The processor 101 controls information processing performed by the server 100 . The processor 101 may be a multiprocessor. Examples of the processor 101 include a CPU, a DSP, an ASIC, an FPGA, an MPU, a PLD, and the like. The processor 101 may be a combination of two or more of the CPU, DSP, ASIC, FPGA, MPU, and PLD.

The RAM 102 serves as a primary storage device of the server 100 . The RAM 102 temporarily stores at least part of the OS program and application programs that are executed by the processor 101 . The RAM 102 also stores various types of data that are used in processing performed by the processor 101 .

The HDD 103 is a secondary storage device of the server 100 . The HDD 103 magnetically writes data to and reads data from an internal magnetic disk. The HDD 103 stores the OS program, application programs, and various types of data. The server 100 may include other types of secondary storage devices such as a flash memory, an SSD, and the like, and may include a plurality of secondary storage devices.

The communication unit 104 is an interface capable of communicating with other computers via the network 10 . The communication unit 104 may be a wired interface or a wireless interface.

The image signal processing unit 105 outputs an image to a display 11 connected to the server 100 , in accordance with an instruction from the processor 101 . Examples of the display 11 include a CRT display, a liquid crystal display, and the like.

The input signal processing unit 106 obtains an input signal from an input device 12 connected to the server 100 , and outputs the input signal to the processor 101 . Examples of the input device 12 include pointing devices (such as a mouse, a touch panel, and the like), a keyboard, and the like.

The disc drive 107 is a drive unit that reads programs and data from an optical disc 13 by using laser beams or the like. Examples of the optical disc 13 include a DVD, a DVD-RAM, a CD-ROM, a CD-R, a CD-RW, and the like. The disc drive 107 reads the programs and data from the optical disc 13 , and stores the read programs and data in the RAM 102 or the HDD 103 , in accordance with an instruction from the processor 101 , for example.

The device connection unit 108 is a communication interface that connects peripheral devices to the server 100 . For example, a memory device 14 and a reader and writer device 15 may be connected to the device connection unit 108 . The memory device 14 is a recording medium having a function for communicating with the device connection unit 108 . The reader and writer device 15 writes data to and reads data from a memory card 16 . The memory card 16 is a card-type recording medium. The device connection unit 108 reads programs and data from the memory device 14 or the memory card 16 , and stores the read programs and data in the RAM 102 or the HDD 103 , in accordance with an instruction from the processor 101 , for example.

FIG. 7 illustrates an exemplary functional configuration of the server 100 according to the second embodiment. The server 100 includes a storage unit 110 , an input unit 120 , a neighboring node calculation unit 130 , a change detection unit 140 , and an output unit 150 . The storage unit 110 may be realized as a storage area reserved in the RAM 102 or the HDD 103 . The input unit 120 , the neighboring node calculation unit 130 , the change detection unit 140 , and the output unit 150 may be realized as modules of software executed by the processor 101 .

The storage unit 110 stores various types of information used in computations performed by the neighboring node calculation unit 130 and the change detection unit 140 . The storage unit 110 may store in advance an adjacency matrix representing nodes and edges in the universal set V at each of a plurality of points of time.

The input unit 120 obtains an adjacency matrix representing nodes and edges in the universal set V at each of a plurality of points of time, and outputs the obtained adjacency matrix to the neighboring node calculation unit 130 . The input unit 120 may obtain the adjacency matrix from another server and store the obtained adjacency matrix in the storage unit 110 .

The description continues in the full USPTO document.