JP5186197B2 - Evaluation apparatus, evaluation method, and evaluation program - Google Patents

Description

  The present invention relates to an evaluation apparatus, an evaluation method, and an evaluation program suitable for use in evaluating an evaluation object by grasping the relationship between an evaluation object such as a company and another object related to the object.

  The relationship between companies is used as an important information source for management decision-making. For example, in the determination of the investment destination and the limit of the loan destination, the risk due to the business relationship or the tie-up relationship of the target company is taken into consideration and used for target selection. Conventionally, a business relationship between companies is grasped by searching a database such as a credit check result or a securities report from an analysis target company (Patent Document 1). Also, in the field of graph theory, there is a known method for assigning a score that considers the degree to which a node is referred to as important for data that considers the object as a node and the relationship between objects as an edge when analyzing the relationship. (Patent Documents 2 to 4, Non-Patent Document 1).

In the method of searching the database in order to grasp the relationship between companies as described above, only the company directly related to the company is considered, and the relationship between companies is grasped from the overall viewpoint such as the business partner of the business partner. There is a problem that cannot be done. In other words, since the interrelation structure behind the company's business partners is not quantified, there is a limit that cannot be evaluated based on the transaction structure.
JP 2003-030467 A JP 2004-240640 A JP 2007-280000 A JP 2006-113900 A J. Kleinberg, "Authoritative sources in a hyperlinked environment." Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46 (1999). Also appears as IBM Research Report RJ 10076, May 1997

  By the way, information that is desired to be known when analyzing a client company includes, for example, risk of chain bankruptcy. Chain bankruptcy is, for example, that a business partner goes bankrupt due to bankruptcy of the business partner or the business partner. Therefore, in order to grasp the risk of chain bankruptcy, it is necessary to grasp information about business partners between companies. However, it is difficult to grasp the relationship between companies that are intricately intertwined by the method of searching a database to grasp the relationship between companies or the method based on the reference relationship so far. It was only to grasp the relationship limited to the previous. For this reason, there is a problem that it is difficult to grasp a structure that exceeds an adjacent relationship such as a business partner.

  The present invention has been made in view of the above circumstances. For example, it is possible to evaluate an evaluation object by grasping a relationship between objects exceeding an adjacent relationship such as a business partner of a company to be evaluated. An object is to provide an evaluation device, an evaluation method, and an evaluation program.

In order to solve the above-described problem, one aspect of the present invention is an evaluation device that evaluates an evaluation target based on related information with a target other than the evaluation target, and is a maximum extracted from the related information. A clique extraction means for extracting a pseudo clique consisting of a union selected to have a certain degree of overlap, and a pseudo-clique that includes an evaluation target among the pseudo cliques extracted by the clique extraction means for each pseudo clique size Based on the frequency calculation means for obtaining the number of cliques and the number of pseudo cliques for each size obtained by the frequency calculation means, the number of pseudo cliques having a size larger than 2 is larger than the number of pseudo cliques having a size of 2. The larger the number, the larger the function that was normalized by the sum of the number of pseudo cliques that contain the evaluation target obtained by the frequency calculation means And evaluated, characterized in that it comprises a cohesion degree calculating means for calculating as a cohesion degree for the subject other than the evaluation target.

In addition, according to one aspect of the present invention, the cohesion degree calculating unit is configured to calculate a pseudo-cuff having a size of 2 based on the sum of the number of pseudo-cliques having a size of 2 or more based on the number of pseudo-cliques for each size obtained by the frequency calculating unit. A value obtained by normalizing the number obtained by subtracting the number of cliques with the sum of the number of pseudo cliques having a size of 2 or more is calculated as the cohesion degree .

One embodiment of the present invention is an evaluation method for evaluating an evaluation target based on related information between the evaluation target and a target other than the evaluation target. The maximum clique extracted from the related information is fixedly overlapped. A clique extraction process for extracting a pseudo clique consisting of a union selected so as to have a degree, and for each pseudo clique size, the number of pseudo cliques that include an evaluation target among pseudo cliques extracted in the clique extraction process is obtained. Based on the frequency calculation process and the number of pseudo cliques for each size obtained in the frequency calculation process, the larger the number of pseudo cliques having a size larger than 2, the larger the number. the function that takes, the normalized value by the sum of the number of pseudo clique that contains the evaluation determined in the frequency calculation process, evaluated, except evaluated Characterized in that it comprises a cohesion degree calculation step of calculating as a cohesion degree for elephants.

One embodiment of the present invention is an evaluation program for evaluating an evaluation object based on related information between the evaluation object and an object other than the evaluation object. The maximum clique extracted from the related information is fixedly overlapped. A clique extraction process for extracting a pseudo clique consisting of a union selected so as to have a degree, and for each pseudo clique size, the number of pseudo cliques that include an evaluation target among pseudo cliques extracted in the clique extraction process is obtained. Based on the frequency calculation process and the number of pseudo cliques for each size obtained in the frequency calculation process, the larger the number of pseudo cliques having a size larger than 2, the larger the number. the function that takes, the normalized value by the sum of the number of pseudo clique that contains the evaluation determined in the frequency calculation process, to be evaluated, the evaluation object Characterized in that it comprises instructions for executing a cohesion degree calculation step of calculating as a cohesion with respect to the outer of the target computer.

  According to the above configuration, the evaluation target is based on the frequency at which the evaluation target is included in the pseudo clique consisting of the union selected so that the maximum clique extracted from the related information indicating whether the evaluation target is related or not has a certain degree of overlap. The degree of cohesion with respect to a target other than the evaluation target is calculated. Therefore, it is possible to evaluate the relationship between the evaluation targets within the union of the maximal cliques. That is, the evaluation object can be evaluated by grasping the relationship between objects exceeding the relationship between adjacent evaluation objects.

  Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a system diagram showing a configuration of an evaluation apparatus and information flow according to the present invention. The evaluation apparatus according to the present embodiment is configured as an input unit 101, a clique extraction unit 102, a calculation unit including a frequency calculation unit 103 and a cohesion degree calculation unit 104, an output unit 105, and a predetermined DB (database). And the storage unit 106. Each unit shown in FIG. 1 is configured by a combination of a computer and its peripheral devices and a program executed by the computer.

  In the input unit 101, an inter-company relationship data table regarding a plurality of companies to be evaluated, a clique extraction parameter in a graph based on the inter-company relation data table, and the like are input. In the calculation unit, various processes are performed, and the degree of cohesion with other companies in each company is calculated. The storage unit 106 stores calculation results (clique extraction result, frequency calculation result). Then, the cohesion degree is output from the output unit 105.

  Here, the premise of the present embodiment will be described. In the evaluation method performed by the evaluation apparatus according to the present embodiment, first, transaction information between a plurality of companies to be evaluated is represented as a graph corresponding to the company to be evaluated as a node and the presence or absence of a transaction as an edge. Express. That is, based on related information such as transaction information between a company to be evaluated and a company other than the object to be evaluated, a graph in which nodes corresponding to two companies having a business relationship are connected by an edge is set. . Here, the graph is defined in the graph theory, and is an edge (branch, arc, etc.) that is a line segment having both ends of several nodes (also called points, vertices, etc.) and pairs of those nodes. It is also expressed as an edge). Such a graph may be represented by a graphic or may be represented by an array process using each element of the array as a node.

If the set of nodes of the graph G is V and the set of edges is E, the graph G is represented by G = (V, E). Further, with respect to a subset E _H of the set E of subsets V _H and the edge of the set V of nodes in the graph G, also both end points of which edge k∈E _H (k represents the elements of the edge set E _H) When included in V _H , the graph H = (V _H , E _H ) is referred to as a subgraph of the graph G. A graph in which all pairs of nodes are connected by edges is called a complete graph.

  A complete graph in the subgraph H of the graph G is called a clique (or a complete subgraph). Such a set of H nodes may be called a clique. Further, the size of the clique H is defined by the number of nodes and is represented by | H |. A clique with n nodes is also called a clique of size n. Further, when the set of nodes of the clique H of the graph G is not truly included in the set of nodes of any other clique, the set H is referred to as a maximal clique of the graph G.

Further, a combination of a plurality of maximal cliques that share a node with a degree equal to or greater than a predetermined threshold (that is, a maximal clique family) is called a pseudo clique. This pseudo clique is a set of extracted maximal cliques in which the number of nodes that do not overlap among the maximal cliques including some overlapping nodes is less than or equal to the predetermined number of nodes. It is called a pseudo clique because it does not always satisfy the definition of clique described above. When C ′ = {C ′ ₁ ,..., C ′ _m } is a maximal clique family of the graph G (that is, a set having maximal cliques C ′ ₁ ,..., C ′ _m as elements), The determined overlap (C ′) is referred to as C ′ redundancy. The degree of overlap takes a value between 0 and 1, and the degree of overlap increases as the value increases.

  Here, ∩ represents a product set of maximal cliques, || represents the number of nodes, and min represents a minimum value.

Further, as shown in the following equation (2), a union (represented by ∪) of maximal cliques C ′ ₁ ,..., C ′ _{m in which} the degree of overlap overlap () exceeds the degree of overlap α which is a constant threshold value. , Defined as pseudo clique PC (C ′). The size of the pseudo clique PC (C ′) is determined by the number of nodes | C ′ | of the pseudo clique PC (C ′). Α is a threshold value for controlling the degree of overlap.

  In the evaluation apparatus of FIG. 1, the input unit 101 inputs an inter-company relationship data table regarding a plurality of companies to be evaluated, a duplication degree α that is a parameter of pseudo clique extraction, and the like. As shown in FIG. 2, the inter-company relationship data table includes, as transaction information, identification information (for example, a company name) indicating a company to be evaluated, and identification information of one or more companies in a business relationship with the company. It is a list which matches (for example, company name). In the example shown in FIG. 2, trading companies of companies whose identification information (here, company name) is “company A” are company names “company B”, “company C”, “company E”, and “company F”. Each company, the trading company of “Company B” is “Company A”, “Company C” and “Company G”, the trading company of “Company K” is “Company E”, “Company H”, “Company I” and “Company J” are indicated.

  Here, with reference to FIG. 3, the graph set with respect to the business relationship data table shown in FIG. 2 is demonstrated. FIG. 3 schematically represents a graph in which a plurality of companies to be evaluated are nodes, and pairs of nodes corresponding to companies having a business relationship are connected by edges. A circle represents a node, and an alphabetic character in the circle represents identification information of the business relationship data table in FIG. 2 (in the example of FIG. 2, the alphabetic part of the company name).

  Next, the function of the clique extraction unit 102 in FIG. 1 will be described with reference to FIG. First, the data and parameters input by the input unit 101 are input to the clique extraction unit 102 (step S11). The input data includes an inter-company relationship data table for setting the graph G = (V, E), the pseudo clique redundancy α, and the like. Here, V corresponds to a set of nodes, and E corresponds to a set of edges.

Next, processing for extracting the maximum cliques C ′ ₁ ,..., C ′ _m is performed on the graph G (step S12). There are various methods for extracting the maximum clique. For example, the following method is used.

  First, select one company from all the companies to be analyzed, create a list of companies that have a link (transaction relationship) with the selected company from the transaction information, and create a list of cliques of size 2 Store in a predetermined table. At this time, combinations having the same value as a set are removed from the table.

  Next, a list of companies that are linked to the companies listed in the size 2 list is created from the transaction information, and stored as a size 3 clique in a predetermined table. Also in this case, combinations with the same value as a set are removed from the table. This is repeated until size 4 and size 5 and new links are not found, and cliques relating to the selected company are extracted.

  The above operation is performed for all companies to be split, the clique that is a complete graph is extracted, and the result is registered in the clique output result table 1. An example of the clique output result table 1 is shown in FIG. In the clique output result table 1 shown in FIG. 5, the extracted number of the maximum clique (identification number), the size, and the constituent elements (node identification information) of the maximum clique are registered. The clique output result table 1 is stored in the storage unit 106 of FIG.

  In addition to the above method, the CLIQUES method, which is a known technique of the maximum clique all-enumeration algorithm, may be used.

  Next, the pseudo clique PC (C ′) is extracted (step S13). Here, from the maximum clique registered in the clique output result table 1, the pseudo clique PC (C ′) that is a combination of the maximum cliques that meets the pseudo clique condition of the expression (2) is extracted. In addition, the number of nodes included in each PC (C ′) is calculated as a clique size.

  In the extraction of the pseudo clique PC (C ′) in step S13, first, all combinations of the maximal cliques extracted in step S12 are created and stored in a predetermined table. Next, the combinations stored in this table are individually taken out, and the overlap degree overlap () of Expression (1) is evaluated. The evaluation result exceeding α is stored in the clique output result table 2 as a pseudo clique. The clique output result table 2 is, for example, a table in the same format as the clique output result table 1 shown in FIG. 5, and the pseudo clique number, the size of the pseudo clique, and the identification information of the node that is a component are registered. Is done. The clique output result table 2 is also stored in the storage unit 106 of FIG.

  Next, the function of the frequency calculation unit 103 in FIG. 1 will be described with reference to FIG. The frequency calculation unit 103 receives the pseudo clique PC (C ′) extracted by the clique extraction unit 102 as input data and the clique size calculated at the time of extraction (step S21).

  Next, frequency information is configured (step S22). In step S22, for each node (each company) included in the pseudo clique PC (C ′), the frequency included in the pseudo clique for each clique size | C′l | is calculated as a matrix, and this is used as the frequency information F. Registered in the frequency information table. Here, l (English letter L) represents the number of the pseudo clique obtained by the clique extraction unit 102. A function representing the frequency information F is shown in the following formula (3), and an example of the frequency information table is shown in FIG.

  In Expression (3), V is a set having the node v as an element, and max (| C′l |) represents the maximum value of the clique size | C′l |.

  In addition, the frequency information table illustrated in FIG. 7 indicates the frequency included in the pseudo clique corresponding to each node (company in FIG. 7) for each pseudo clique size. For example, it is shown that the node of “company A” is included once in a pseudo clique with a clique size of 2 and once in a pseudo clique with a clique size of 3. This frequency information table is stored in the storage unit 106 of FIG.

  Next, the function of the cohesion degree calculation unit 104 in FIG. 1 will be described with reference to FIG. The cohesion degree calculation unit 104 receives the frequency information F calculated by the frequency calculation unit 103 as input data (step S31). Next, a degree of cohesion indicating the degree of cohesion between nodes (that is, between companies) is configured (step S32). In step S32, the cohesion degree u (v) for each node (for each company) is calculated based on the following formula (4) using the frequency information F, and is registered in the cohesion degree output result table. FIG. 9 shows an example of the cohesion degree output result table. In the cohesion degree output result table of FIG. 9, cohesion degree and node identification information (in FIG. 9, company ID (recognition code)) are registered.

  In Expression (4), v is a node, k is a natural number of 2 or more, and the cohesion degree u (v) is defined by a value from 0 to 1, and the larger the value, the more the mutual engagement between the connection destinations of the node. Represents being strong. The final output result in the evaluation apparatus according to the present embodiment is obtained from the cohesion degree output result table by the output unit 105.

  FIG. 10 collectively shows the function and processing flow of the present embodiment described with reference to FIGS. As described above, the evaluation apparatus according to the present embodiment sets a graph G that represents a company as a node and a transaction presence / absence as an edge based on the relationship between the companies, and serves as an evaluation index based on the size of the pseudo clique in the graph G. The degree of cohesion is calculated. This degree of cohesion is obtained by the following procedure.

(1) The prepared business relationship is represented by a graph in which the business is a node and the business relationship is an edge.

(2) A pseudo clique is extracted from the graph (step S41 in FIG. 10). First, (a) all maximal cliques are enumerated using the above-described method or another maximal clique full enumeration algorithm (for example, CLIQUES). (B) Next, a pseudo clique is configured by combining the listed maximal cliques.

(3) For the pseudo clique configured in (2) above, frequency information is obtained for each clique size of the node to be evaluated. Specifically, for each node included in G = (V, E) representing a network between nodes as a graph, the size | C′l | of each pseudo clique C′l (∈C ′) is included. A matrix having the frequency as an element is calculated as frequency information using equation (3) (step S42).

(4) Next, a cohesion degree is calculated using the equation (4) for the frequency information obtained in (3) (step S43). The degree of cohesion is defined by a value from 0 to 1, and the larger the value, the stronger the mutual engagement between the connection destinations of the node.

(5) Then, depending on the degree of cohesion, it can be evaluated that the mutual relationship between suppliers is strong when the cohesion degree is large, and the mutual relationship between suppliers is weak when the cohesion degree is small. Therefore, in the example of credit analysis, when evaluating the company, it is possible to treat each customer as a customer based on the degree of cohesion, or to give credit by the customer itself.

  In addition, as a result of the evaluation according to this embodiment for a plurality of companies that actually exist, there is a certain tendency in the structure of the graph depending on the degree of cohesion, and the structure of the graph can be classified. confirmed. That is, when the graph structure of a company with a high degree of cohesion and a company with a low degree of cohesion was confirmed, the company with a high degree of cohesion has a dense transaction structure as shown in FIG. The company has confirmed that the graph has a star-shaped transaction structure as shown in FIG. In FIGS. 11 and 12, nodes are indicated by rectangles and edges are indicated by line segments.

  According to the present invention, the following effects can be obtained. (1) Evaluation is promoted by visualizing the transaction structure of a company, together with a quantitative value called cohesion that can classify the strength of mutual relationships between companies. (2) By comparing the degree of cohesion for a plurality of companies to be evaluated, it can be used for decision making such as selection of the scope of credit investigation and selection of business partners. (3) Depending on the value of the cohesion degree with respect to the evaluation target company, it is possible to determine a transaction structure between a dense type in which transactions are made with each other and a star type in which transactions are performed mainly with a specific company. As a result, for example, when the degree of cohesion is large, it is strongly influenced by other companies, so it is necessary to conduct a survey including companies behind it. When the degree of cohesion is small, the evaluation company is the main link, and the scope of the survey is sufficient for the evaluation target company, making it easy to determine the scope of the survey target company. (4) By comparing multiple companies to be evaluated based on the degree of cohesion, it becomes easier to narrow down the companies, such as setting the scope of credit checks and selecting suppliers and suppliers, and it is expected to reduce the number of analysis work steps it can.

  The evaluation object according to the present invention is not limited to the above-described transactions between companies, and can be applied to a wide range of fields as long as the relationship between events can be expressed by nodes and edges.

  The embodiment of the present invention is not limited to the above. For example, the units shown in FIG. 1 can be integrated or divided, or can be distributed and arranged via communication means. The embodiment of the present invention can be configured by a combination of a computer and a program executed by the computer, and a part or all of the program is distributed via a computer-readable recording medium or a communication line. Is possible.

<Example 1>
Next, a description will be given of results of an experiment in which an evaluation according to the present embodiment is performed on a plurality of companies that actually exist. The contents of the experiment were to calculate the cohesion degree using the purchase and sales transaction information of the company, and to examine whether or not the type of transaction relationship can be classified based on the cohesion degree. The data used for the experiment is purchase and sales transaction information of 2903 listed companies in Nikkei NEEDS = 2003. The network data configuration method showing the relationship between the companies is such that the network data is represented by a graph G, and when the company i is a node, the relationship between the company i and the company j is set by the edge gij of the graph G. Depending on whether there is a business relationship between purchase and sale, gij = 1 if there is, and gij = 0 if there is none.

  The extraction result of the pseudo clique is shown in FIG. FIG. 13 shows a list of pseudo cliques (top 20) arranged in descending order of size and business types of companies belonging to each size. The number of companies is shown in parentheses. From the extraction result of the pseudo clique, it can be seen that the general trading company and the automobile industry community, which are known to have many customers, are extracted. These have many relationships with sales partners and suppliers and are appropriate as extracted pseudo cliques. Thereby, it becomes possible to grasp which community the partner company belongs to.

  FIG. 14 shows the calculation result of the cohesion degree together with the total frequency of each size. Regarding the frequency, the frequency of size 2 is shown by hatching. It was confirmed that the value of cohesion was low in general trading companies and wholesale retailers where the mutual relationship between suppliers was not strong, and the cohesion value was high in the automobile industry where the mutual relationship between suppliers was strong.

  Regarding the dense and star type classification of the graph structure, for example, in Company A in the car body and other industries, the dense structure shown in FIG. 11, that is, the transaction structure of a company with a high degree of cohesion is confirmed. It was done. On the other hand, in the company “a” which is a retail business, the star-shaped structure shown in FIG.

It is a block diagram which shows the structural example of the evaluation apparatus by this invention. It is a figure which shows an example of the company relationship data table input into the input part 101 of FIG. It is the figure which represented the business relationship data table of FIG. 2 with the graph. It is a figure which shows the flow of a process in the clique extraction part 102 of FIG. It is a figure which shows an example of the clique output result table 1 produced in the clique extraction part 102 of FIG. It is a figure which shows the flow of a process in the frequency calculation part 103 of FIG. It is a figure which shows an example of the frequency information table produced by the frequency calculation part 103 of FIG. It is a figure which shows the flow of a process in the cohesion degree calculation part 104 of FIG. It is a figure which shows an example of the cohesion degree output result table produced by the cohesion degree calculation part 104 of FIG. It is a system diagram which shows the flow of a series of processes in the evaluation apparatus of FIG. It is a figure which shows an example of the graph structure of a company with the high cohesion degree actually calculated by embodiment of this invention. It is a figure which shows an example of the graph structure of a company with the low cohesion degree actually calculated by embodiment of this invention. It is a figure which shows the result of having actually extracted the pseudo clique by embodiment of this invention. It is a figure which shows the result of having actually calculated the cohesion degree by embodiment of this invention.

Explanation of symbols

DESCRIPTION OF SYMBOLS 101 ... Input part 102 ... Clique extraction part 103 ... Frequency calculation part 104 ... Cohesion degree calculation part 105 ... Output part 106 ... Memory | storage part

Claims (4)

An evaluation device that evaluates the evaluation object based on related information between the evaluation object and an object other than the evaluation object,
Clique extraction means for extracting a pseudo clique consisting of a union selected so that the maximal clique extracted from the related information has a certain degree of overlap;
Frequency calculation means for obtaining the number of pseudo cliques that include the evaluation object among the pseudo cliques extracted by the clique extraction means for each pseudo clique size ;
Based on the number of pseudo cliques for each size obtained by the frequency calculation means, a function that takes a larger value as the number of pseudo cliques having a size larger than 2 is larger than the number of pseudo cliques having a size of 2. Is a value obtained by normalizing the sum of the number of pseudo cliques including the evaluation object obtained by the frequency calculation means as a degree of cohesion of the evaluation object with respect to an object other than the evaluation object. An evaluation apparatus comprising: and. The cohesion degree calculating means is a number obtained by subtracting the number of pseudo cliques having a size of 2 from the sum of the number of pseudo cliques having a size of 2 or more based on the number of pseudo cliques for each size obtained by the frequency calculating means. 2. The evaluation apparatus according to claim 1 , wherein a value obtained by normalizing the number of pseudo cliques having a size of 2 or more is calculated as the cohesion degree . An evaluation method for evaluating an evaluation object based on information related to an object other than the evaluation object,
A clique extraction process for extracting a pseudo clique consisting of a union selected so that the maximum clique extracted from the related information has a certain degree of overlap;
For each pseudo clique size , a frequency calculation process for determining the number of pseudo cliques that include the evaluation target among the pseudo cliques extracted in the clique extraction process, and
Based on the number of pseudo cliques for each size obtained in the frequency calculation process, a function that takes a larger value as the number of pseudo cliques having a size larger than 2 is larger than the number of pseudo cliques having a size of 2. A cohesion degree calculation step of calculating a value normalized by the total number of pseudo cliques including the evaluation object obtained in the frequency calculation process as a cohesion degree of the evaluation object with respect to an object other than the evaluation object; The evaluation method characterized by including. An evaluation program that evaluates the evaluation object based on information related to an object other than the evaluation object,
A clique extraction process for extracting a pseudo clique consisting of a union selected so that the maximum clique extracted from the related information has a certain degree of overlap;
For each pseudo clique size , a frequency calculation process for determining the number of pseudo cliques that include the evaluation target among the pseudo cliques extracted in the clique extraction process, and
Based on the number of pseudo cliques for each size obtained in the frequency calculation process, a function that takes a larger value as the number of pseudo cliques having a size larger than 2 is larger than the number of pseudo cliques having a size of 2. A cohesion degree calculation step of calculating a value normalized by the total number of pseudo cliques including the evaluation object obtained in the frequency calculation process as a cohesion degree of the evaluation object with respect to an object other than the evaluation object; An evaluation program comprising instructions for execution by a computer.

Images