JP6596794B2 - Quality degradation estimation device, quality degradation estimation method, and program - Google Patents

Description

  The present invention relates to a technique for estimating / determining how much degradation has occurred among connection points of nodes in communication by using an end-to-end quality measurement value in communication as an input.

  In mobile communications, quality degradation occurs in various places due to diversification of user environments and diversification of usage methods. In order to improve the quality of mobile communication services, it is important to understand the degradation location.

  However, although it is possible to perform end-to-end measurement in quality measurement, it is difficult to determine the degree of deterioration at each location (server, ISP, access node, terminal, etc.) from the measurement result. As a prior art regarding this point, there is a technique disclosed in Patent Document 1. Patent Document 1 discloses a technique for finding a degraded node among a plurality of nodes from end-to-end measurement values of a communication network including a plurality of nodes.

JP2015-115672A

  When using a measured value of End-to-End in a scene where a degraded node is identified by estimating the value of the degradation amount for each node that constitutes the communication network from the measured value of End-to-End, Data cannot always be collected for all combinations of nodes, and there are data deficiencies. However, in the technique disclosed in Patent Document 1, when there is data loss, the estimation accuracy is greatly reduced.

  The present invention has been made in view of the above points, and when estimating the value of the degradation amount for each node using the measured value of End-to-End in the communication network, even if data loss exists, It aims at providing the technique which makes it possible to suppress the fall of estimation accuracy.

According to an embodiment of the present invention, a quality degradation estimation device for estimating quality degradation of nodes constituting a communication network,
The communication network is
It is composed of a first node group having graph information and having a similarity in deterioration values between adjacent nodes, and a second node group having no graph information and having sparseness that there are a small number of degradation points,
Input means for inputting a quality measurement value between two nodes, path information in each measurement, and a graph Laplacian matrix corresponding to the structure of a graph representing the similarity of deterioration between nodes in the first node group ;
The relationship that the vector composed of the quality measurement values of each measurement is equal to the product of the matrix composed of the path information of each measurement and the vector composed of the value of the degradation amount of each node, and the graph Laplacian matrix Computing means for simultaneously calculating an estimated value of the deterioration amount of each node of the first node group and the second node group by solving an estimation formula derived based on a matrix in which eigenvectors are arranged;
An output means for outputting an estimated value of the deterioration amount of each node or information obtained based on the estimated value is provided.

Further, according to the embodiment of the present invention, there is provided a quality degradation estimation method executed by a quality degradation estimation apparatus that estimates quality degradation of nodes constituting a communication network,
The communication network is
It is composed of a first node group having graph information and having a similarity in deterioration values between adjacent nodes, and a second node group having no graph information and having sparseness that there are a small number of degradation points,
An input step of inputting a quality measurement value between two nodes, path information in each measurement, and a graph Laplacian matrix corresponding to a structure of a graph representing similarity of deterioration between nodes in the first node group ;
The relationship that the vector composed of the quality measurement values of each measurement is equal to the product of the matrix composed of the path information of each measurement and the vector composed of the value of the degradation amount of each node, and the graph Laplacian matrix A calculation step of simultaneously calculating an estimated value of the deterioration amount of each node of the first node group and the second node group by solving an estimation formula derived based on a matrix in which eigenvectors are arranged;
An output step of outputting an estimated value of the degradation amount of each node or information obtained based on the estimated value is provided.

  According to the embodiment of the present invention, when estimating the degradation amount value for each node using the end-to-end measurement value in the communication network, even if there is a data loss, the estimation accuracy is reduced. It becomes possible to suppress.

It is a block diagram of the quality degradation estimation apparatus 100 in embodiment of this invention. It is a figure for demonstrating the example of an input. It is a figure for demonstrating the example of an input. It is a figure for demonstrating the node structure in an Example. It is a figure which shows the original signal of the object of estimation. It is a figure which shows the trial average of RMSE.

  Hereinafter, an embodiment (this embodiment) of the present invention will be described with reference to the drawings. The embodiment described below is merely an example, and the embodiment to which the present invention is applied is not limited to the following embodiment. In this embodiment, a “node” constituting a communication network (hereinafter referred to as a target communication network) that is a target of quality degradation estimation is a single network device (eg, server, router, switch, base station, Terminal, etc.) as well as a configuration composed of a set of network devices such as an ISP and a carrier network. The target communication network is not limited to a specific type of network, and may be, for example, a mobile network, a fixed network, or a network in which a mobile network and a fixed network are mixed. However, other nets may be used.

  In the present embodiment, each node constituting the target communication network has a value, and the larger the value, the larger the deterioration amount. Then, the quality degradation estimation device 100 specifies a degradation node having a large value among the nodes constituting the communication network from the quality measurement value between any two nodes (end-to-end quality measurement), or Estimate the value of each node. Hereinafter, the apparatus configuration and processing contents will be described.

(Device configuration)
FIG. 1 shows a configuration diagram of a quality degradation estimation apparatus 100 in the present embodiment. As shown in FIG. 1, the quality degradation estimation apparatus 100 includes an input unit 101 that inputs data used for quality degradation estimation, a computation unit 102 that performs quality degradation estimation, and an output unit 103 that outputs the result of the computation. And a data storage unit 104 that stores input data, mid-calculation data, calculation results, programs, and the like.

  The quality degradation estimation apparatus 100 in the present embodiment can be realized by causing a computer to execute a program describing the processing contents described in the present embodiment. That is, the function of the quality degradation estimation apparatus 100 can be realized by executing a program corresponding to processing executed in the apparatus using hardware resources such as a CPU and a memory built in the computer. Is possible. The above-mentioned program can be recorded on a computer-readable recording medium (portable memory or the like), stored, or distributed. It is also possible to provide the program through a network such as the Internet or electronic mail.

(Operation of the quality degradation estimation apparatus 100)
Next, as an operation of the quality degradation estimation apparatus 100, the procedure of the quality degradation estimation method in the present embodiment will be described in detail.

<Input>
The following three data are input to the input unit 101 of the quality degradation estimation apparatus 100. The input data is stored in the data storage unit 104, and is read out and calculated by the calculation unit 102 in the subsequent processing.

Input 1: Quality measurement between any two nodes in the target communication network;
Input 2: Route information when input 1 is measured (node ID composing communication between two points);
Input 3: A graph structure representing the similarity of deterioration between nodes and the components of the nodes included in the graph.

  Regarding the input 3, it is possible to have a plurality of graphs. However, one node belongs to one graph. As an example, in each of the node group 1 and the node group 2 in the target communication network, there is a similarity of degradation between adjacent nodes, and there is no similarity of degradation between the node group 1 and the node group 2 There are two graphs, a graph of node group 1 and a graph of node group 2. Regarding input 3, the graph may be an unweighted graph or a weighted graph. The case where there is no graph (when I = 0 below) is not excluded. That is, even when there is no graph, it is possible to estimate the deterioration node / deterioration amount.

  In the present embodiment, the definitions of variables and the like shown below are used.

Number of nodes in the target communication network: M
Node ID: a_1, ..., a_M
Number of measurements: K
Number of graphs: I (constant satisfying 1 ≦ I ≦ M / 2)
Input 1 (quality measurement value between two arbitrary nodes): z_k (k = 1, ..., K)
Input 2 (matrix representing path information (nodes composing communication) in measurement k (k = 1,..., K)): A
A of input 2 is a matrix of (measurement number K) × (node number M). In the k-th row of this matrix, 1 is set in the column of nodes that are routed or end points in communication at the measurement value z_k, and 0 is set in the column of nodes that are not routed and are not end points (k = 1,..., K).

Input 3 (graph structure representing similarity of degradation between nodes and components of nodes included in the graph): graph Laplacian L_i for undirected graph G_i composed of the number of nodes N_i and nodes that are components of the graph ID (where 2≤N_i <M, i = 1, ..., I). Even when there are a plurality of graphs at input 3, each node does not become an element of two or more graphs.
<Details of input 3>
Here, regarding the input 3, a method for obtaining the graph Laplacian L constituting the graph G of the number N of nodes will be described.

  First, a distance d between nodes included in the graph G is defined. This distance d is an index representing the similarity of deterioration between nodes. The distance d can be, for example, a geographical distance, but is not limited thereto, and may be any value as long as the similarity is a decreasing function of the distance d. The attenuation function is defined as f (x).

  The graph Laplacian L is calculated by L = D-C. C and D are as follows.

  C: Adjacency matrix (N × N matrix. C_jk, which is an element of C, is 0 when j = k and satisfies c_jk = c_kj (j, k = 1,..., N)). The c_jk when j = k is different between the unweighted graph and the weighted graph as follows.

  Unweighted graph: For the distance d_jk between the j and k-th nodes, c_jk = 1 if f (d_jk) is greater than or equal to a certain threshold value e, and c_jk = 0 otherwise.

  Weighted graph: c_jk = f (d_jk) when the distance between the jth and kth nodes is d_jk.

  D: Degree matrix (N × N matrix. G_jk, which is an element of D, is a diagonal matrix (j, k = 1,..., N) when j ≠ k). Further, g_jj = Σ_ {k = 1} ^ {N} c_jk. That is, g_jj is the sum of c_jk from k = 1 to N.

<Specific examples of input 1 to input 3>
A specific example of inputs 1 to 3 will be described with reference to FIGS. FIG. 2 is an example of a node configuration used for explaining the specific example, and nodes having node IDs: 1,..., 5 are connected as illustrated.

  As shown in FIG. 3, input 1 (quality measurement value between two arbitrary nodes) in this example is a measurement value of three times (K = 3). FIG. 3 also shows node paths for each of measurement 1, measurement 2, and measurement 3.

  Input 2 (matrix representing path information at measurement k (k = 1,..., K)) is matrix A as shown. Each row corresponds to each measurement, and 1 is set in the position of the column corresponding to the passing node.

  Input 3 in FIG. 3 (a graph structure representing the similarity of deterioration between nodes and the components of the nodes included in the graph) shows an example without weight. In the adjacency matrix C, in this example, 1 is set between nodes connected by the line in FIG. 2 on the assumption that f (d_jk) is equal to or greater than the threshold value e. In the order matrix D, values calculated based on the values set in the adjacency matrix C are set. The graph Laplacian L is calculated by DC.

  In the present embodiment, the input 3 (graph Laplacian L) may be calculated in advance outside the quality degradation estimation device 100 and input to the quality degradation estimation device 100, or may be input to the quality degradation estimation device 100. By giving the information of the graph G and the distance d to the unit 101, the calculation unit 102 may calculate the graph Laplacian L and store it in the data storage unit 104.

<Processing procedure for estimating quality degradation>
Next, a process for estimating quality degradation performed by the calculation unit 102 based on the inputs 1 to 3 will be described. Basically, the result of the process executed by the calculation unit 102 is stored in the data storage unit 104, and is read and used by the calculation unit 102 in the next process.

First, the computing unit 102 calculates eigenvalues λ_i, l of L_i for the graph Laplacian L_i of the undirected graph G_i composed of the number of nodes N_i (l = 1,..., N_i, 0 = λ_i, 1 ≦ λ_i, 2 ≦ ... ≦ λ_i, N_i), eigenvectors u_i, l (l = 1,..., N_i) corresponding to eigenvalues are obtained, and a matrix U in which eigenvectors are arranged is created. Here, U is an orthonormal matrix. I = 1,...
U_i = (u_i, 1,…, u_i, l,…, u_i, N_i) (N_i × N_i matrix)… Equation (1)
Next, the nodes in the graph G_i are arranged in ascending order of node IDs, and new IDs are a ′ _ {i_1},..., A ′ _ {i_N_i}. Assume that the value of each node is x_i, 1,..., X_i, N_i (i = 1,... I). Also, nodes that do not belong to the graph (P, P = M -Σ_ {i = 1} ^ {I} N_i) are also arranged in ascending order of node IDs, and the new IDs are a "_1, ..., a" _P, respectively The node values of y_1,. Note that the value of each node is an object to be estimated, and x_i, 1, ..., x_i, N_i (i = 1, ... I), y_1, ..., y_P are variables.

  Furthermore, from the matrix A (the matrix of (number of observations K) x (number of nodes M)) representing the path information (connection nodes) in the measurement k (k = 1, ..., K), only the columns of nodes included in the graph G_i Is created (i = 1,..., I) (a number of observations K) × (number of nodes N_i)). Even for nodes that do not belong to the graph, a matrix A "((number of observations K) x (number of nodes) that extracts only columns of nodes that do not belong to the graph from A (matrix of number of observations K) x (number of nodes M)) P) matrix).

Here, when the value of each node a_1, ..., a_M is x_1, ..., x_M,
(z_1, ..., z_K) ^ T = A (x_1, ..., x_M) ^ T (where T is transposed) ... Equation (2)
Meet. This expression indicates that the sum of the values of the nodes on the path (including the end points) in the measurement is the quality measurement value.

  Equation (2) can be rewritten as follows using the matrix A_i (i = 1,..., I) and the matrix A ″.

(z_1,…, z_K) ^ T = A_1 (x_1,1,…, x_1, N_1) ^ T +… + A_i (x_i, 1,…, x_i, N_i) ^ T
+ ... + A_I (x_I, 1, ..., x_I, N_I) ^ T + A "(y_1, ..., y_P) ^ T (where T is transposed) ... Equation (3)
Furthermore, it is assumed that the values x_i, 1, ..., x_i, N_i (i = 1, ..., I) of the graph G_i can be decomposed by the product of the prepared U_i and the spectrum vector s_i as shown in the following equation (4). .

(x_i, 1,…, x_i, N_i) ^ T = U_i s_i (i = 1,…, I)… Equation (4)
Let vector s_i, vector y = (y_1, ..., y_P) ^ T. The vector s_i is a vector having N_i elements.

  Substituting equation (4) into equation (3) yields the equation (z_1,…, z_K) ^ T = A_1 U_1 s_1-…-A_i U_i s_i-…-A_I U_I s_I-…-A "y It is done.

As described above, since a relationship in which the relationship between the observation (measurement value) vector and the unknown vector is expressed linearly is obtained, the calculation unit 102 solves the linear inverse problem based on the above relationship, thereby obtaining the vector s_1 ,..., S_I, y are estimated and further transformed to estimate a vector (x_1,..., X_M) ^ T that is the original value of each node. Specifically, it is as follows. Hereinafter, Lasso (Least absolute shrinkage and selection operator) is used as an estimation method, but estimation may be performed by a method other than Lasso. Lasso is a normalized estimation method using the sum of absolute values of regression coefficients (L ₁ norm) as a normalization term. For example, “Seung-Jean Kim; Stanford Univ., Stanford; Koh, K.; Lustig, M.; Boyd, S. et al.“ An Interior-Point Method for Large-Scale l1- Regularized Least Squares "".

  Specifically, the arithmetic unit 102 estimates vectors s_1,..., S_I, y by solving a Lasso estimation expression expressed by the following equation (5) using sparse approximation.

(s_1,…, s_I, y) (estimated) = argmin_ {s_1,…, s_I, y} 1/2 || (z_1,…, z_K) ^ T-A_1U_1s_1-…-A_iU_is_i-…-A_IU_Is_I-… -A "y || ^ 2 + μ_1 | s_1 | +… + μ_i | s_i | +… + μ_I | s_I | + μ" | y |… (5)
Equation (5) is: 1/2 || (z_1,…, z_K) ^ T-A_1U_1s_1-…-A_iU_is_i-…-A_IU_Is_I-…-A "y || ^ 2 + μ_1 | s_1 | +… + μ_i | s_i | +... + μ_I | s_I | + μ "| y |” represents the estimation of vectors s_1,. Μ_1,..., Μ_I, μ ″ in Equation (5) are Lasso parameters.

  Reconstruct x_i, 1, ..., x_i, N_i (i = 1, ..., I) by using vectors s_1, ..., s_I estimated from Eq. (5) as U_1, ..., U_I (Equation (4) X_i, 1,..., X_i, N_i, (i = 1,... I), and y_1,..., Y_P are obtained. The obtained result is stored in the data storage unit 104.

<Output>
Subsequently, the output unit 103 outputs the obtained result. In the present embodiment, the output unit 103 can perform any one, any plurality, or all of the following five types of outputs.

Output 1: Value for each node Output 2: Relative value for each node Output 3: Top n items with large values Output 4: Presence or absence of nodes with large values Output 5: Number of nodes with large values Below, more concrete Explained.

  In the output 1, the output unit 103 outputs x_i, 1,..., X_i, N_i, (i = 1,... I), and y_1,.

  In the output 2, the output unit 103 extracts the minimum value of the quality measurement values z_k (k = 1,..., K) from the data storage unit 104, and x_i, 1,..., X_i, N_i, (i = 1,. ) Is subtracted from each of the quality measurement values z_k (k = 1, ..., K) (min (z_1, ..., z_K)), and the obtained values and y_1, ..., y_P are output. To do.

  In the output 3, the output unit 103 determines the minimum quality measurement value z_k (k = 1,..., K) from all the results (x_i, 1,..., X_i, N_i, (i = 1,... I) of the output 2 Of M values obtained by subtracting the values (min (z_1,..., Z_K)) and y values of y_1,..., Y_P), n are extracted and output in descending order.

  In output 4, a threshold value is set, and output section 103 labels two variables with and without deterioration depending on whether or not there is a value equal to or greater than the threshold value among M results of output 2. Is output.

  Output 5: A threshold is set, and the output unit 103 counts the number of nodes having a value equal to or greater than the threshold among the M results of output 2, and outputs the counted result.

  Outputs 1 to 5 are examples, and outputs other than these may be performed.

<Application of graph creation method>
If the output result has already been obtained several times, the distance d is updated from the similarity of the estimated value of each node, the graph Laplacian is recalculated by the method already explained, and the graph Laplacian is used as an input again. The estimation may be performed.

(Example)
An embodiment as a more specific example in the case where the quality degradation estimation apparatus 100 performs quality degradation estimation by the method described above will be described.

  In this embodiment, as shown in FIG. 4, there are two types of nodes, an access node and a server. There are 25 access nodes and 10 servers (total number of nodes M = 35). Further, as shown in FIG. 4, it is assumed that 25 access nodes have graph information due to geographical restrictions. FIG. 4 shows that the servers 1 and 5 and the access nodes 1 to 3, 6 to 8, and 11 to 13 are deteriorated.

  In this embodiment, a delay time when an arbitrary access node i (i = 1,..., 25) and an arbitrary server j (j = 1,..., 10) are connected is measured as a quality measurement value. . In this embodiment, the number of measurements is K and each delay time is z_k (k = 1,..., K). This is input 1. As for measurement items, it is possible to use throughput, packet loss rate, etc. in addition to the delay time. However, when an index indicating deterioration is used as the value is small, deterioration is indicated as the value is large. A function to convert to use such an index is used.

  The connection information in the measurement k (k = 1,..., K) is represented by an A matrix. This is input 2. The row A represents the number of times of measurement, and the columns are arranged in the order of the access nodes 1 to 25 and the servers 1 to 10, and 1 is set in the node of the route in the measured communication. For example, if access node 1 and server 3 are connected in the k-th measurement and no other node is passed between access node 1 and server 3, the k-th row of matrix A is (1,0 , 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 , 1,0,0,0,0,0,0,0).

  As described above, it is assumed that the 25 access nodes have graph information due to geographical restrictions. In this embodiment, the graph Laplacian L is calculated using a weightless graph expressing the presence / absence of connection as 0, 1, and the input 3 And The servers 1 to 10 do not have graph information.

  Based on the above assumption, the quality degradation estimation apparatus 100 estimates values (x_1,..., X_25, y_1,..., Y_10) indicating degradation of each access node and each server.

  Step 1) When input 1 to input 3 are input to quality degradation estimation apparatus 100, operation unit 102 obtains eigenvalues / eigenvectors of graph Laplacian matrix L of the graph of the access node, and arranges eigenvectors in ascending order of eigenvalues. Create a matrix U.

U = (u_1,…, u_25) (25 × 25 matrix)
Step 2) The computing unit 102 divides the matrix A into a matrix A_a (K × 25 matrix) having access node columns and a matrix A_s (K × 10 matrix) having server columns.

  The values x_1,..., X_25, y_1,..., Y_10 of each access node and each server satisfy the following expressions.

(z_1, ..., z_K) ^ T = A_a (x_1, ..., x_25) ^ T + A_s (y_1, ..., y_10) ^ T (T is transposed) ... Equation (6)
From the graph structure, the values x_1,..., X_25 of each access node can be expressed as follows using the spectrum vector s = (s_1,..., S_25) ^ T.

(x_1, ..., x_25) ^ T = Us ... Equation (7)
When equation (6) is rewritten using equation (7), the result is as follows.

(z_1,…, z_K) ^ T = A_a U s + A_s (y_1,…, y_10) ^ T… Equation (8)
Step 3) Set the vector s = (s_1, ..., s_25) ^ T, y = (y_1, ..., y_10) ^ T. The computing unit 102 estimates the vector s, y by solving the following equation using the sparse approximation of the vector s, y.

(s ', y') (estimate) = argmin_ {s, y} 1/2 || (z_1,…, z_K) ^ T-A_a U s-A_sy || ^ 2 + μ_1 | s | + μ_2 | y | ... Formula (9)
Μ_1 and μ_2 in Eq. (9) are Lasso parameters.

  For example, the data storage unit 104 has a program for solving equation (9). The calculation unit 102 creates the matrix U and divides the matrix A, and then executes the program to input known information to Equation (9) and perform an operation for estimating the vectors s and y.

  Step 4) The computing unit 102 converts the estimated vector s ′ = (s′_1,..., S′_25) ^ T into estimated values x′_1,. To do.

Us' = (x'_1,…, x'_25) ^ T
Step 5) From the above, estimated values x′_1,..., X′_25, y′_1,..., Y′_10 of each access node and each server are obtained, and the output unit 103 outputs these values. . This is an example when output 1 is performed.

(Effect of embodiment)
In the present embodiment, when nodes having different characteristics are mixed in a node, the value of the node is estimated by using two characteristics of the value similarity between the nodes and the sparsity of the node having the value. The similarity of values between nodes is incorporated as graph structure information. For example, as described in the embodiment, when there is a node having two types of attributes, that is, a server and an access node, the server uses the sparsity that the number of degradation points is small, and the access node is geographically By expressing the similarity of degradation between adjacent nodes as a graph from the above dependency and using the method according to the present invention, the estimation accuracy is improved compared to the case where the node characteristics are not considered.

  Also, in this embodiment, the quality measurement value that is input does not include a measurement value that passes through any node that is a component of the graph (the input data is missing). There is an effect of suppressing the decrease in accuracy by complementing from the proximity data.

  The evaluation result at the time of making a problem setting as an Example is shown. Here, as shown in FIG. 4, a situation is assumed in which deterioration occurs in two of the ten servers and nine of the 25 access locations. Further, it is assumed that the value of the node to be estimated is given as shown in FIG. In FIG. 5, it is shown that the values of the degraded servers 1 and 5, the access nodes 1 to 3, 6 to 8, and 11 to 13 are 100, and the other values are 0.

  When there are measurement values for all combinations of each server and each access node (250 data), when data loss is randomized and the measurement values to be input are reduced (25, 50, 75, 100, 125, 150) , 175, 200 data) is shown in FIG. The vertical axis in FIG. 6 represents the average of RMSE (Root Mean Squared Error) when 1000 trials are performed. Comparing the method of the present invention (GF + CS) and the existing method (NNCS) (reference: Patent Document 1), the method of the present invention is less apt to be less accurate when data is lost.

  That is, in the technique of the present invention, by using the relationship between nodes based on prior knowledge or the like as a graph structure, it is possible to compensate for data loss from the graph structure, and to determine degraded nodes at fewer measurement points and The amount of deterioration of each node can be estimated. Further, since data loss can be tolerated, it is possible to determine a degraded node and estimate the degradation amount of each node with a smaller amount of calculation due to a reduction in input data.

(Summary of embodiment)
As described above, according to the present embodiment, a quality degradation estimation apparatus that estimates quality degradation of nodes constituting a communication network, including quality measurement values between two nodes, path information in each measurement, and , An input means for inputting a graph Laplacian matrix corresponding to a graph structure representing the similarity of deterioration between nodes, and a vector composed of quality measurement values of each measurement, a matrix composed of path information of each measurement By solving an estimation equation derived based on the relationship that is equal to the product of the degradation value of each node and a vector composed of the degradation amount values of each node and a matrix in which the eigenvectors of the graph Laplacian matrix are arranged, Computational means for calculating an estimated value of the amount, and an output means for outputting the estimated value of the deterioration amount of each node or information obtained based on the estimated value Quality degradation estimation device is provided.

  The input unit 101, the calculation unit 102, and the output unit 103 described in the embodiment are examples of an input unit, a calculation unit, and an output unit, respectively.

  The graph Laplacian matrix is a matrix obtained by subtracting the adjacency matrix of the graph from the degree matrix of the graph. In addition, the estimation formula is derived based on, for example, the relationship and a relationship in which a vector composed of the deterioration amount value of each node is equal to a product of a matrix in which the eigenvectors are arranged and a spectrum vector. , Lasso's estimation formula.

  Although the present embodiment has been described above, the present invention is not limited to the specific embodiment, and various modifications and changes can be made within the scope of the gist of the present invention described in the claims. Is possible.

DESCRIPTION OF SYMBOLS 100 Quality degradation estimation apparatus 101 Input part 102 Calculation part 103 Output part 104 Data storage part

Claims (7)

A quality degradation estimation device for estimating quality degradation of nodes constituting a communication network,
The communication network is
It is composed of a first node group having graph information and having a similarity in deterioration values between adjacent nodes, and a second node group having no graph information and having sparseness that there are a small number of degradation points,
Input means for inputting a quality measurement value between two nodes, path information in each measurement, and a graph Laplacian matrix corresponding to the structure of a graph representing the similarity of deterioration between nodes in the first node group ;
The relationship that the vector composed of the quality measurement values of each measurement is equal to the product of the matrix composed of the path information of each measurement and the vector composed of the value of the degradation amount of each node, and the graph Laplacian matrix Computing means for simultaneously calculating an estimated value of the deterioration amount of each node of the first node group and the second node group by solving an estimation formula derived based on a matrix in which eigenvectors are arranged;
An output means for outputting an estimated value of the deterioration amount of each node or information obtained based on the estimated value. The quality degradation estimation apparatus according to claim 1, wherein the graph Laplacian matrix is a matrix obtained by subtracting an adjacency matrix of the graph from an order matrix of the graph. The estimation formula is derived based on the relationship and a relationship in which a vector composed of deterioration values of each node is equal to a product of a matrix in which the eigenvectors are arranged and a spectrum vector. The quality deterioration estimation device according to claim 1, wherein the quality deterioration estimation device is an equation. A quality degradation estimation method executed by a quality degradation estimation device that estimates quality degradation of nodes constituting a communication network,
The communication network is
It is composed of a first node group having graph information and having a similarity in deterioration values between adjacent nodes, and a second node group having no graph information and having sparseness that there are a small number of degradation points,
An input step of inputting a quality measurement value between two nodes, path information in each measurement, and a graph Laplacian matrix corresponding to a structure of a graph representing similarity of deterioration between nodes in the first node group ;
The relationship that the vector composed of the quality measurement values of each measurement is equal to the product of the matrix composed of the path information of each measurement and the vector composed of the value of the degradation amount of each node, and the graph Laplacian matrix A calculation step of simultaneously calculating an estimated value of the deterioration amount of each node of the first node group and the second node group by solving an estimation formula derived based on a matrix in which eigenvectors are arranged;
An output step of outputting an estimated value of the degradation amount of each node or information obtained based on the estimated value. A quality degradation estimation method comprising: The quality degradation estimation method according to claim 4, wherein the graph Laplacian matrix is a matrix obtained by subtracting an adjacency matrix of the graph from an order matrix of the graph. The estimation formula is derived based on the relationship and a relationship in which a vector composed of deterioration values of each node is equal to a product of a matrix in which the eigenvectors are arranged and a spectrum vector. The quality deterioration estimation method according to claim 4, wherein the quality deterioration estimation method is an equation.   The program for functioning a computer as each means in the quality degradation estimation apparatus of any one of Claims 1 thru | or 3.

Images