JP5340232B2 - Graph diameter monitoring apparatus, method and program - Google Patents

Description

  The present invention relates to a graph diameter monitoring apparatus, method, and program, and more particularly, to a graph diameter monitoring apparatus, method, and program for monitoring an ever-increasing graph diameter.

  A graph is a data structure that expresses what exists in the real world and their relationship in the form of nodes and edges. Due to its intuitive expression method, graphs are widely used in the fields of mathematics and computer science.

  The distance between nodes in a graph is one of the basic features in graph theory. The diameter of the graph is a feature amount based on the distance between the nodes, and is very important in analyzing the graph. However, the graph targeted by the conventional graph theory is static, and there is a premise that the number of nodes and edges does not change.

  In recent years, it has become necessary to handle graph data in which the number of nodes increases with time, resulting in hundreds of thousands or more of nodes. This is the result of an environment that uses a huge database and the Internet. In recent years, the characteristics of graph data that continues to grow while increasing the number of nodes from moment to moment are becoming clear (see, for example, Non-Patent Document 1). Therefore, there is an increasing demand for efficient processing of graphs that grow from moment to moment and eventually become very large in size.

  The present invention deals with the problem of continuously detecting the diameter from a graph that continues to grow from moment to moment.

  A P2P (point-to-point) network can be cited as an application example of the problem targeted by this specification.

  In recent years, Gnutella (registered trademark),

OceanStore（登録商標）などP2Pサービスに対する注目が集まっている。P2Pは中心にサーバを置くのではなくネットワークを介して計算リソースを共有するところに大きな特徴がある（例えば、非特許文献２参照）。

Attention has been focused on P2P services such as OceanStore (registered trademark). P2P has a major feature in that it does not place a server at the center but shares computing resources via a network (for example, see Non-Patent Document 2).

  Among the applications using P2P, content distribution using the Internet is one of the most important ones attracting attention from many researchers. For example, Kazaa and its variants are growing rapidly, and it is known that 4.5 million or more users share 7 petabytes or more of content (for example, see Non-Patent Document 3). In these applications, each computer transfers data to each other and distributes content.

  The number of computers with which each computer communicates directly is limited by the protocol used in the network. The most important problem when designing a network is how many computers each computer communicates directly with (see, for example, Non-Patent Document 4). This issue is important for two reasons. The first reason is that the number of computers connected to the network is enormous, and the number of computers that communicate directly can be very large. In addition, since data transfer between computers is overhead, it is necessary to reduce the number of transfers for efficient distribution.

  Diameter in the network is an important indicator for efficient content distribution. This is because the diameter corresponds to the maximum number of transfers between computers in the network (see, for example, Non-Patent Document 5). Efficient content distribution becomes possible by increasing the number of computers with which each computer communicates directly only when the diameter increases.

  In addition to the above, improving network robustness is another important application. Koppula et al. Showed how the edge of the network can be improved by plotting the diameter of a dynamically changing graph (see, for example, Non-Patent Document 6).

Newman, The Structure and Function of Complex Networks, SIREV: SIAM Review, 2003 Stephanos Androutsellis-Theotokis and Diomidis Spinellis, A survey of peer-to-peer content distribution technologies, ACM comput. Surv., 2004. Mayank Bawa, Brian F. Cooper, Arturo Crespo, Neil Daswani, Prasanna Ganesan, Hector Garcia-Molina, Sepandar D. Kamvar, Sergio Marti, Mario T. Schlosser, Qi Sun, Patrick Venograd and Beverly Yang, Peer-to-peer research at Stanford, SIGMOD Record, 2003. Sylvia Ratnasamy, Ion Stoica and Scott Shenker, Routing Algorithms for DHTs: Some Open Questions, IPTPS, 2003. AAbhishek Kumar, Shashidhar Merugu, Jun Xu and Xingxing Yu.Ulysses: A Robust, Low-Diameter, Low-Latency Peer-to-Peer Network, ICNP, 2003. Hema Swetha Koppula, Kumar Puspesh and Nily Ganguly, Study and Improvement of Robustness of Overlay Networks, HiPC, 2007.

Conventionally, calculation time of O (n ² + nm) (n and m are the number of nodes and edges, respectively) is required, which is not practical for analyzing large-scale graphs.

  The present invention has been made in view of the above points, and the diameter in the graph can be obtained at a higher speed than before, and the approximation of the graph is efficiently calculated even if the original graph grows momentarily. It is an object of the present invention to provide a graph diameter monitoring apparatus, method, and program capable of being used.

In order to solve the above problems, the present invention (Claim 1) is a graph diameter monitoring device for monitoring the diameter of a graph having a data structure that expresses the relationship of what exists in the real world with nodes and edges. Because
Data receiving means for receiving nodes that change at each time;
A storage unit storing a received node (additional node), a pair of solution nodes, which is a set of two nodes one hour before the distance between the nodes becomes a diameter, and a diameter that is the maximum distance between the nodes;
A distance calculating means for calculating a distance between nodes;
A pruning means for obtaining a maximum distance from the node stored in the storage means to another node by the distance calculation means, and pruning a node that cannot be a diameter;
Updating means for updating a pair of nodes having a diameter of the storage means based on a distance from the node added by the data receiving means.

Further, the present invention (Claim 2) provides the pruning means,
A reference node that is the highest-order node is selected from the additional node stored in the storage unit and the solution node one time ago, and the distance calculation unit is used to determine the solution node one time before the storage unit. Means for calculating a candidate distance from the pair, estimating a maximum value of a distance to other nodes with respect to a peripheral node of the reference node, and excluding the node from a search target if the maximum value is smaller than the candidate distance Including.

Further, according to the present invention (Claim 3), in the updating means,
Means for updating the pair of solution nodes and the diameter of the storage means in response to whether the diameter is increased, decreased or not changed by the node added by the data receiving means.

Moreover, this invention (Claim 4) is the update means,
If the maximum distance is larger than the diameter one hour before stored in the previous storage means, the diameter is set as the maximum distance, the solution node pair of the storage means is updated, and the maximum distance is calculated as If there is a pair of nodes having the same length, the pair of solution nodes in the storage means is updated using the distance from the additional node, and if there is no pair having the same distance as the diameter one time ago, the distance calculating means Means for determining the diameter.

The present invention (Claim 5) is a graph diameter monitoring method for monitoring the diameter of a graph having a data structure that expresses the relationship of what exists in the real world with nodes and edges,
A storage means storing a received node and a pair of solution nodes, which is a set of two nodes one hour before the distance between the nodes becomes a diameter, a diameter that is the maximum distance between the nodes, a data receiving means, and a node In a device having a distance calculation means for obtaining a distance between, a pruning means, an updating means,
A data receiving step in which the data receiving means receives a node that changes at each time; and
The pruning means obtains the maximum distance from the node stored in the storage means to other nodes by the distance calculation means, and prunes a node that cannot be a diameter;
The updating unit performs an updating step of updating a pair of nodes having a diameter of the storage unit based on a distance from the node added by the data receiving unit.

Further, the present invention (Claim 6) provides the pruning step,
A reference node that is the highest-order node is selected from the additional node stored in the storage unit and the solution node one time ago, and the distance calculation unit is used to determine the solution node one time before the storage unit. The candidate distance is calculated from the pair, the maximum value of the distance to the other nodes with respect to the peripheral node of the reference node is estimated, and if the maximum value is smaller than the candidate distance, the node is excluded from the search target.

Further, according to the present invention (Claim 7), in the updating step,
A method of updating the pair of solution nodes and the diameter of the storage means according to whether the diameter is increased, decreased, or not changed by the node added by the data receiving step.

Further, according to the present invention (Claim 8), in the updating step,
If the maximum distance is larger than the diameter one hour before stored in the previous storage means, the diameter is set as the maximum distance, the solution node pair of the storage means is updated, and the maximum distance is calculated as If there is a pair of nodes having the same length, the pair of solution nodes in the storage means is updated using the distance from the additional node, and if there is no pair having the same distance as the diameter one time ago, the distance calculating means Obtain the diameter.

  Moreover, this invention (Claim 9) is a program for functioning a computer as each means which comprises the diameter monitoring apparatus of the graph of any one of Claim 1 thru | or 4.

  As described above, the conventional technique is not practical for analyzing a large-scale graph, but according to the present invention, the diameter can be obtained at a significantly high speed. The graph approximation can be calculated efficiently even if the original graph grows from moment to moment.

  Further, according to the present invention, nodes that cannot be solved by approximation are pruned, but the obtained solution is accurate.

  In addition, according to the present invention, since the necessary parameter is automatically determined, the user does not need to adjust the parameter.

It is a block diagram of the monitoring apparatus in one embodiment of this invention. 3 is an algorithm for pruning a reference node according to an embodiment of the present invention. It is a change in the diameter of the graph. It is an algorithm of the sequential update in one embodiment of this invention.

  Embodiments of the present invention will be described below with reference to the drawings.

  In the present embodiment, the following problems are targeted.

<Problem>
Find the diameter in the graph:
Given: Unweighted undirected graph G [t] at time t = (V, E):
Find: G [t] diameter value and the node pair that gives it:
Here, V and E are a set of nodes and edges, respectively. Although this problem is directed to unweighted undirected graphs, the present invention can be applied to both weighted and directed graphs.

  The present invention can be applied not only to the addition of nodes but also to the addition of edges and the deletion of nodes / edges.

  FIG. 1 shows a configuration of a monitoring apparatus according to an embodiment of the present invention.

  The monitoring apparatus shown in FIG. 1 includes a data receiving unit 10, a distance calculating unit 20, a data storage unit 30, and a detecting unit 40.

  The data receiving unit 10 receives a node that changes at each time and transfers it to the distance calculation unit 20 and the data storage unit 30. The distance calculation unit 20 calculates a distance between nodes. The data storage unit 30 stores an additional node input from the data receiving unit 10 and a pair of a graph (a diameter that is the maximum distance between the nodes) and a solution node one hour before. The detection unit 40 selects a reference node and calculates a diameter in the graph.

  First, symbols used in this specification are defined and necessary background knowledge is explained.

  Real-world networks can be expressed as graph G = (V, E). Here, V is a set of nodes, and E is a set of edges. N and m are the numbers of nodes and edges, respectively. That is, n = | V | and m = | E |.

The “path from the node u to the node v” is a sequence of edges starting from the node u and ending at the node v. The path with the fewest nodes is called the “shortest path”. The distance between node u and node v is the total number of edges included in the shortest path,
Total number of edges = d (u, v)
Is defined. From the definition, d (u, u) = 0 for the node u∈V, and d (u, v) = d (v, u) for the node u, v∈V.

  The diameter of the graph is defined as the maximum distance between nodes as follows:

[Definition 1] (Diameter)
In the graph G = (V, E), when the maximum distance between nodes is max (d (u, v) | u, vεV), the diameter D is defined as follows.

D = max (d (u, v) | u, v∈V) (1)
The present invention calculates not only the diameter of the graph, but also the set D of pairs of nodes that will be the diameter. D is defined as follows:

[Definition 2] (pair of solution nodes)
A pair D of nodes whose diameter is a distance between nodes is defined as follows.

D = {(u, v) | d (u, v) = D} (2)
Conventionally, breadth-first search has been used to accurately calculate the diameter of the graph. Breadth-first search is a technique widely used in graph search. In the breadth-first search, when a graph G = (V, E) is given, the distance is gradually calculated while following the surrounding nodes that can be reached from the starting node u. In the existing method for calculating the centrality of the node u, the distance from the node u to all other nodes is calculated using a breadth-first search, and the sum of the distances is calculated.

In order to calculate the diameter using the breadth-first search, a calculation amount of O (n ² + nm) is required. This is because a breadth-first search that requires a calculation amount of O (n + m) for all n nodes is performed. Therefore, when the graph becomes large, this processing requires a huge amount of calculation. Further, since this process is repeated for a graph that grows from moment to moment, because the graph grows, it is not realistic to obtain the diameter from the node by the breadth-first search.

  In contrast, according to the present invention, the detection unit 40 performs “pruning by reference nodes” and “sequential update”.

(A) Pruning by reference node:
In this method, the detection unit 40 prunes a node that cannot be a diameter at high speed in order to reduce high calculation time.

  In the conventional method, since the breadth-first search is performed from all n nodes, the calculation cost is very high.

  In the present invention, instead of calculating the distance from all the nodes, the node of the highest degree (hereinafter referred to as “reference node”) is selected from the nodes that are not pruned, and the distance from only the reference node is selected. It is as simple as calculating.

  The detection unit 40 selects reference nodes one by one, and estimates whether surrounding nodes can be a pair of solution nodes based on the distance between the reference node and other nodes to be pruned. That is, pruning of the surrounding nodes is performed by the reference node. The estimation for each neighboring node can be performed in the calculation time of O (1). Therefore, when the number of reference nodes is k (k << n), the diameter can be obtained with a calculation time of O (kn + km).

  This approach has two advantages. One is that a nearby node that is close to the reference node is pruned by an estimated value, but the diameter can be accurately obtained. In other words, this method can safely prun a node that cannot be solved in a short calculation time. Further, the number k of reference nodes is automatically determined. In general, algorithm parameters greatly affect the performance of the algorithm, and the determination thereof is complicated. However, the present invention automatically determines the parameters and does not require the user to determine the parameters.

(B) Sequential update:
The sequential update is one in which the diameter increases, shrinks, or does not change after nodes are added to the graph that grows from moment to moment. This is a process for efficiently updating the diameter after the node is added, and is performed by the detection unit 40.

  Although the diameter can be obtained at high speed by pruning with the reference node, recalculation with the reference node is required each time the graph grows. This method is to avoid pruning by the reference node every time the graph grows. As will be discussed later, if the diameter does not shrink with the addition of a node, the diameter can be updated only with the distance from the added node.

  This method is especially effective for graphs that grow from moment to moment. This is because the number of added nodes is smaller than that of the existing nodes, and the graph does not change greatly before and after the addition.

  The pruning by the reference node (A) and the sequential update (B) will be described below.

  First, the method (A) will be described in detail.

  In the method (A), a reference node is selected, and a node that cannot be a diameter is pruned (excluded from the search target).

  Pruning by the reference node is performed as follows.

  (1) The distance calculation unit 20 calculates a candidate distance that is expected to increase the distance from the reference node to another node, and outputs the candidate distance to the detection unit 40.

  (2) The detection unit 40 selects a reference node that is expected to have a shorter distance to other nodes.

  (3) The detection unit 40 estimates the maximum value of the distance to other nodes with respect to the peripheral nodes of the reference node stored in the data storage unit 30.

  (4) If the estimated maximum value is smaller than the candidate distance, the detection unit 40 prunes the node.

  Here, a method for estimating the maximum distance with respect to the node will be described first, and it will be shown that the estimated value becomes the upper limit value of the maximum distance. A method for selecting a reference node in the detection unit 40 and a method for obtaining a candidate distance in the distance calculation unit 20 will be described.

  Formally, the maximum value of the distance from one node u in the graph to another node stored in the data storage unit 30 is defined as follows.

[Definition 3] (Maximum distance)
The maximum value d _max (u) of the distance to other nodes in the graph G is defined as follows.

d _max (u) = max (d (u, v) | v∈V) (3)
The estimated maximum distance is defined as follows:

[Definition 4] (estimated value)
When the reference node with respect to v nodes of the graph G has a u _r, estimate the maximum distance

を以下のように定義する。

Is defined as follows.

推定値は以下に述べるように、距離の最大値の上限値となる性質がある。

As described below, the estimated value has a property of being an upper limit value of the maximum distance value.

[Lemma 1] (Upper limit)
The following properties hold for all nodes in graph G.

証明）
ノードvからの距離がd_max (v)であるノードをｗとすると以下の式が成り立つ。

Proof)
When a node whose distance from the node v is d _max (v) is w, the following equation is established.

よって成り立つ。

Therefore it holds.

  As will be described later, the distance calculation unit 20 can obtain an accurate diameter using this property.

  If the estimated value is shorter than the candidate distance, the node is pruned. As can be seen from definition 4 above, the estimated value can be calculated by the calculation time of O (1), and thus the diameter can be calculated efficiently.

  If the maximum distance of the reference node is long and the candidate distance is short, the pruning cannot be efficiently performed. Therefore, the selection of the reference node and the candidate distance is important for effective pruning. In the present invention, the node with the highest degree is selected as the reference node among the unpruned nodes that may be the diameter among all the nodes in the data storage unit 30. This is because the maximum distance of such nodes is expected to be small.

  In the present invention, a candidate distance is calculated from a pair of solution nodes one hour before. This is because the pair of nodes is expected to be a long distance because the graph hardly changes even when nodes are added.

  Algorithm 1 in FIG. 2 shows a pruning technique using reference nodes.

Here, the degree of the node u is deg (u). In algorithm 1,
1) First, the candidate distance is calculated using the solution pair one hour before in the data storage unit 30 (first line).

  2) Then, a reference node is obtained based on the degree (line 5).

  3) If the maximum distance of the reference node is greater than or equal to the candidate distance, the solution node pair is updated (lines 7-13).

  4) The algorithm is used for pruning candidate distances. That is, if the estimated value at a certain node is smaller than the candidate distance, the node is pruned (line 15).

  These processes are repeated until all nodes are processed. In this algorithm, the number of reference nodes is automatically determined.

  Next, the sequential updating method (B) will be described.

  In this method, the detection unit 40 sequentially updates solution node pairs in order to detect the diameter at high speed. Since there is no need to perform pruning by the reference node every time the graph grows, more efficient detection is possible.

  First, the nature of the distance between nodes after the graph has grown is described. Then, the necessary and sufficient conditions of (1) increase in diameter, (2) shrink, (3) no change are clarified.

Here, it is assumed that _a node u _a is newly added to the data storage unit 30 every hour.

  First, after a node is added, it shows that the distance between the nodes which exist before adding does not increase.

[Lemma 2] (Distance between nodes after node addition)
The distance between nodes at time t is not longer than the distance between nodes at graph G _{t-1 at} time t-1.

  (Proof) If the shortest paths of nodes u and v at time t pass through the additional node, there is no corresponding path at time t-1. That is, the shortest path at time t−1 is shortened by the additional node. Otherwise, there is a shortest path between nodes u and v that does not pass through the additional node at time t. That is, the same path exists at time t-1. As a result, the distance between nodes u and v is not increased by the addition of nodes.

  Although the diameter changes after the node is added, the above property is used to clarify the condition that the diameter of the graph changes. An example in which the diameter of the graph changes is shown in FIG. In FIG. 3, the original existing node is expressed as a white circle, and the newly added node is expressed as a gray circle.

  First, conditions for increasing the graph will be described.

  A necessary and sufficient condition for the graph to be large is that the maximum distance of the added node is larger than the diameter one hour before.

[Auxiliary Theorem 3] (Necessary and sufficient condition for increasing diameter)
Necessary and sufficient conditions for increasing the diameter of the graph are as follows.

d _max (u _a )> D _t-1 (7)
(Proof) If D _t > D _t−1 , the maximum distance of all existing nodes cannot be longer than D _t−1 by Lemma 2, so the maximum distance of node u _a is Become. Also, if d _max (u _a )> D _t−1 , obviously d _max (u _a ) = D _t and D _t > D _t−1 holds.

  The necessary and sufficient condition for the diameter of the graph to shrink is that the maximum distance of the additional node is shorter than the diameter one hour before, and the addition of the node shortens the distances of all solution node pairs one hour before.

[Auxiliary Theorem 4] (Necessary and sufficient condition for diameter reduction)
Necessary and sufficient conditions for reducing the diameter of the graph are as follows.

証明）もし、D_t < D_t-1であれば、定義２よりd_max (u_a)< D_t-1でありかつ１時刻前の全ての解ノードのペアの距離がD_t-1より短くなる。またもし式（１）と式（２）が成り立つのであれば定義２と補助定理２よりグラフの直径は時刻ｔで短くなる。

Proof) If D _t <D _t-1 , then d _max (u _a ) <D _t-1 from definition 2 and the distances of all solution node pairs one hour before are from D _t-1 Shorter. If Equations (1) and (2) hold, the diameter of the graph becomes shorter at time t from Definition 2 and Lemma 2.

  A necessary and sufficient condition that the diameter of the graph does not change is that there is a pair of solution nodes one hour before that the maximum distance of the additional node is the same as the diameter one hour before or the distance is not reduced by adding a node.

[Auxiliary Theorem 5] (Necessary and sufficient condition that the diameter does not change)
The necessary and sufficient conditions for the diameter of the graph not to change are as follows.

証明）補助定理３と４より明らか。

Proof) It is clear from Lemma 3 and 4.

  The diameter can be detected efficiently by sequentially updating the solution node pairs. First, it is shown that confirmation of whether the distance of the pair of solution nodes one hour before becomes shorter using the distance from the additional node, and details of the present invention using sequential update will be described.

  In order to update the pair of solution nodes, the present invention uses the following properties in the shortest path (for example, “Ulrik Brandes, A Faster Algorithm for Betweenness Centrality, Journal of Mathematical Sociology, 2001”).

[Auxiliary Theorem 6] (Bellman criterion)
The necessary and sufficient condition that the node u is on the shortest path between the nodes v and w is as follows.

d (u, v) + d (u, w) = d (v, w) (10)
Theorem 6 can be used to confirm whether adding a node shortens the distance between solution node pairs one hour before.

[Auxiliary Theorem 7] (Confirmation of distance)
Necessary and sufficient conditions for the node ua to shorten the distance of the solution node pair (v, w) one hour before in the graph that grows momentarily are as follows.

d (v, u _a ) + d (w, u _a ) <D _t-1 (11)
Proof) If the node u _a long as it reduce the distance node u _a is the shortest path on the node v and w. Therefore, from Lemma 6
D _t-1 > d (v, w) = d (u _a , v) + d (u _a , w)
Holds.

Also, if
d (v, u _a ) + (d (w, u _a ) <D _t-1
Then the additional node u _a
D _t-1 > d (u _a , v) + d (u _a w) ≥ d (v, w)
Since this holds, reduce the distance.

  According to Theorem 7, if the diameter of the graph increases or does not change, the solution node pairs can be updated sequentially from the distance of the additional nodes. That is, if the additional node has a diameter, the detection unit 40 updates the solution node pair using the distance from the additional node. Also, if the additional node shortens the distance of the pair of solution nodes one hour ago, this is efficiently obtained using the lemma 7. If there is no pair of nodes having the same length as the diameter one hour before, the distance calculation unit 20 obtains the diameter using pruning by the reference node.

  FIG. 4 shows a sequential update algorithm.

  (1) First, the maximum distance of the added node is obtained (first line).

  (2) If the maximum distance is larger than the diameter of the previous time stored in the data storage unit 30, it becomes the new diameter (Lemma Theorem 3). Write to the storage unit 30 (3rd to 5th lines).

  (3) If there is a pair of nodes whose maximum distance is the same as the diameter one hour ago or the same length as the diameter one hour ago, the diameter will not change even if a node is added (Lemma Theorem 5) . Therefore, in this method, the solution node pair is updated using the distance from the additional node, and is written in the data storage unit 30.

  (4) Also, if there is no pair of nodes with the same distance as the diameter one hour before, the diameter shrinks (Auxiliary Theorem 4), and the distance is calculated by the algorithm 1 of FIG. 15th to 17th lines).

The graph grows while increasing the number of nodes, but it is assumed that there is one node at time t = 1 for simplicity. Therefore, at time t = 1, D _t−1 = 0 and D _t−1 ≠ 0.

  The discussion has been made on the assumption that one node is added so far, but the present invention can cope with the case where a plurality of nodes are added. If an edge is added, processing is performed assuming that a node connected to the edge is added. When the node / edge is deleted, the diameter is obtained by the algorithm 1 in FIG.

  Next, the fact that the present invention can accurately detect the diameter and the amount of calculation will be shown.

  Note that the number of reference nodes is k.

[1] Accuracy of diameter detection First, it will be shown that the present invention can accurately detect the diameter.

[Lemma Theorem 8] (accurate detection)
The present invention can accurately detect the diameter.

  Proof) It is proved by mathematical induction that the present invention can perform accurate detection at time t (≧ 1).

First, it is shown that accurate detection can be performed at time t = 1. It shows that accurate detection can be performed at time t = 1. At time t = 1, the present invention indicates that D ₁ = 0 and D ₁ = (u ₁ , u ₁ ) (1) D _t−1 = 0 and D _t−1 ≠ 0,
(2) Since d _max (u ₁ ) = 0, it can be obtained (see the 8th to 12th lines of algorithm 2 in FIG. 4).

  In addition, when accurate detection can be performed at time t = k, it indicates that accurate detection can also be performed at time t = k + 1. If the diameter does not shrink at time t = k + 1, the present invention can perform accurate detection using Lemma 7. Otherwise, the present invention determines the diameter by pruning with a reference node. Here, if the estimated value is smaller than the candidate distance, the node is pruned, but the estimated value has an upper limit value (Auxiliary Theorem 1). For this reason, a node having a diameter cannot be pruned. Therefore it holds.

[2] Calculation Volume Here, the calculation volume of the conventional method is described first, and then the calculation volume of the present invention is described.

[Auxiliary Theorem 9] (conventional method)
In order to obtain the diameter by the conventional method, a memory amount of O (n + m) and a calculation time of O (n ² + nm) are required.

  Proof) The conventional method requires a memory amount of O (n + m) in order to maintain the graph in the neighbor list representation. In addition, a calculation time of O (n + m) is required for each of the distances from all n nodes.

[Auxiliary Theorem 10] (memory capacity of the present invention)
The present invention requires a memory amount of O (n + m).

  Proof) The present invention requires a memory amount for holding a graph and a memory amount for holding a pair of solution nodes, but the number of solution node pairs is very small in proportion to the number of nodes / edges. Therefore, the present invention requires a memory amount of O (n + m).

[Auxiliary Theorem 11] (Calculation time of the present invention)
In the present invention, a calculation time of O (n + m) is necessary when the diameter does not shrink, and a calculation time of O (kn + km) is necessary when the diameter shrinks.

  Proof) The present invention first calculates the distance from the added node and checks whether the diameter is reduced. The calculation time required for this is O (n + m). If the diameter shrinks, the present invention finds the diameter by pruning with a reference node, but the computation time in this case is O (km + km).

  In the present invention, the operation of the components of the monitoring apparatus shown in FIG. 1 can be constructed as a program, installed in a computer used as the monitoring apparatus and executed, or distributed via a network. .

  Further, the constructed program can be stored in a portable storage medium such as a hard disk, a flexible disk, or a CD-ROM, and can be installed or distributed in a computer.

  The present invention is not limited to the above-described embodiment, and various modifications and applications can be made within the scope of the claims.

DESCRIPTION OF SYMBOLS 10 Data receiving part 20 Distance calculation part 30 Data storage part 40 Detection part

Claims (9)

A graph diameter monitoring device for monitoring the diameter of a graph having a data structure that expresses the relationship of what exists in the real world with nodes and edges,
Data receiving means for receiving nodes that change at each time;
A storage unit storing a received node (additional node), a pair of solution nodes, which is a set of two nodes one hour before the distance between the nodes becomes a diameter, and a diameter that is the maximum distance between the nodes;
A distance calculating means for calculating a distance between nodes;
A pruning means for obtaining a maximum distance from the node stored in the storage means to another node by the distance calculation means, and pruning a node that cannot be a diameter;
Updating means for updating a pair of nodes as a diameter of the storage means based on a distance from the node added by the data receiving means;
An apparatus for monitoring the diameter of a graph, comprising: The pruning means includes
A reference node that is the highest-order node is selected from the additional node stored in the storage unit and the solution node one time ago, and the distance calculation unit is used to determine the solution node one time before the storage unit. Means for calculating a candidate distance from the pair, estimating a maximum value of a distance to other nodes with respect to a peripheral node of the reference node, and excluding the node from a search target if the maximum value is smaller than the candidate distance The graph diameter monitoring device of claim 1, comprising: The updating means includes
2. A means for updating the pair of solution nodes and the diameter of the storage means according to whether the diameter is increased, decreased or not changed by the node added by the data receiving means. Monitoring device for the diameter of the described graph. The updating means includes
If the maximum distance is larger than the diameter one hour before stored in the previous storage means, the diameter is set as the maximum distance, the solution node pair of the storage means is updated, and the maximum distance is calculated as If there is a pair of nodes having the same length, the pair of solution nodes in the storage means is updated using the distance from the additional node, and if there is no pair having the same distance as the diameter one time ago, the distance calculating means Means for determining the diameter by
The graph diameter monitoring device of claim 1, comprising: A method for monitoring the diameter of a graph for monitoring the diameter of a graph having a data structure that expresses the relationship of what exists in the real world with nodes and edges,
A storage means storing a received node and a pair of solution nodes, which is a set of two nodes one hour before the distance between the nodes becomes a diameter, a diameter that is the maximum distance between the nodes, a data receiving means, and a node In a device having a distance calculation means for obtaining a distance between, a pruning means, an updating means,
A data receiving step in which the data receiving means receives a node that changes at each time; and
The pruning means obtains the maximum distance from the node stored in the storage means to other nodes by the distance calculation means, and prunes a node that cannot be a diameter;
An update step in which the update means updates a pair of nodes that is the diameter of the storage means based on the distance from the node added by the data reception means;
A method for monitoring the diameter of a graph, characterized by: In the pruning step,
A reference node that is the highest-order node is selected from the additional node stored in the storage unit and the solution node one time ago, and the distance calculation unit is used to determine the solution node one time before the storage unit. A candidate distance is calculated from the pair, a maximum value of a distance to other nodes with respect to a peripheral node of the reference node is estimated, and if the maximum value is smaller than the candidate distance, the node is excluded from search targets. 5. The method for monitoring the diameter of the graph according to 5. In the updating step,
6. The graph according to claim 5, wherein the pair of solution nodes and the diameter of the storage means are updated according to whether the diameter is increased, decreased, or not changed by the node added by the data receiving step. Diameter monitoring method. In the updating step,
If the maximum distance is larger than the diameter one hour before stored in the previous storage means, the diameter is set as the maximum distance, the solution node pair of the storage means is updated, and the maximum distance is calculated as If there is a pair of nodes having the same length, the pair of solution nodes in the storage means is updated using the distance from the additional node, and if there is no pair having the same distance as the diameter one time ago, the distance calculating means Find the diameter by
6. The diameter monitoring method for a graph according to claim 5.   The program for functioning a computer as each means which comprises the diameter monitoring apparatus of the graph of any one of Claims 1 thru | or 4.

Images