Abstract:
A covariance-clustering algorithm for partitioning a graph into sub-graphs (clusters) using variations of the pseudo-inverse of the Laplacian matrix (A) associated with the graph. The algorithm does not require the number of clusters as an input parameter and, considering the covariance of the Markov field associated with the graph, algorithm finds sub-graphs characterized by a within-cluster covariance larger than an across-clusters covariance. The covariance-clustering algorithm is applied to a semantic graph representing the simulated evidence of multiple events.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
       [0001]    The present application claims the benefit of U.S. Provisional Patent Application Ser. No. 61/652,723, filed on May 29, 2012, entitled “Method of Analyzing a Graph with a Covariance-Based Clustering Algorithm Using a Modified Laplacian Pseudo-Inverse Matrix,” the contents of which are hereby incorporated by reference 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    The present invention pertains to the art of analyzing a knowledge base of narrative text containing information describing evidence for various events in a scenario and organizing the events and information in a format for statistical analysis using mathematical tools which enable an analyst to identify groups or clusters of related information within the knowledge base. 
         [0003]    Currently, several nations are facing threats from violent actions taken against them from foreign countries, international terrorists and/or internal organizations that resort to violent actions. In order to counteract or prevent these violent acts, organizations, such as government agencies and in some cases corporations, employ analysts to try to predict when such violent actions will occur. 
         [0004]    Generally, the organizations start by collecting information about suspected groups. Such information may be gathered from several sources. For example, computer based communications, such as E-mails, may be intercepted and the contents or summaries of the E-mails stored. Telephone intercepts may be translated and also stored, usually as narrative text. Other information may come from police reports describing the results of searches of people that have been arrested. In some cases, reports may come from military units that capture people or computers having information of interest. In each case, threat analysts usually express scenarios as narrative text using written language. Each entry will generally describe basic information about an event. Specifically, the entry often will include an entity who committed certain acts, what they did, when they did it, where the acts took place, etc. However, the entries and other evidence are often fragmentary and not organized in a meaningful way. 
         [0005]    While such information may be useful directly and each narrative report may provide valuable information, often truly useful information needed to predict a violent action may only become apparent when information from various different sources is cross-referenced and analyzed together. Of particular interest is finding a series of events that all relate to each other. The task of figuring out if the events are directed to one or more distinct targets is also desirable, but not easy determinable. Collecting and organizing information from a large number of sources and converting the information into a format that can be easily analyzed has proven to be a difficult task. 
         [0006]    U.S. Pat. No. 7,225,122 proposes a method for analyzing computer communications to produce indications and warnings of dangerous behavior. The method includes collecting a computer-generated communication, such as a piece of electronic mail, and parsing the collected communication to identify categories of information that may be indicative of the author&#39;s state of mind. When the system identifies an author who represents a threat, then appropriate action may be taken. However, the method only focuses on electronic communications and determining the state of mind of an author. The method does not address any other predictors of when and where a violent event may occur or how multiple communications may be related. Also, the method does not organize the information in a format that may be statistically analyzed by mathematical tools. Instead, the method focuses on using Weintraub algorithms to profile psychological states of an author. 
         [0007]    U.S. Patent Application Publication No. 2007/0061758 discloses a method for processing natural language so that text communications may be displayed as diagrammatic representations. This patent document does not address analyzing threat scenarios or even pulling information from different sources and organizing the information. 
         [0008]    Algorithms to find partitions of a graph based on a spectrum of a Laplacian matrix date back to the 1970s. Existing methods generally use the eigenvectors associated with the smallest non-zero eigenvalues of the Laplacian matrix of a semantic graph G. The eigenvector v 2  associated with the 2 nd  smallest eigenvalue λ 2  of the Laplacian matrix associated with a graph is often used to partition a graph into clusters. The eigenvalue λ 2  is called the ‘algebraic connectivity’ of the graph shown in  FIG. 6 , and the corresponding eigenvector v 2  is called ‘Fiedler vector’. A plot of the sorted components of the Fiedler vector of a graph is produced in  FIG. 10 . Most of the existing partitioning algorithms use this plot to find clusters. However, no evident clusters can be singled out from this plot. A plot of the sorted components of the Fiedler vector of the transformed Laplacian matrix is shown in  FIG. 11 . Again, no clusters are distinguishable. 
         [0009]    As can be seen from the above discussion, there exists a need in the art for a method providing a structural representation of a scenario that takes narrative text from various sources and produces a format that may be statistically analyzed with mathematical tools and, more particularly, to develop mathematical tools and algorithms that allow analysts to effectively anticipate plausible terrorist attacks given fragmentary evidence (intelligence and other information) stored in knowledge base represented by a semantic graph and to determine which pieces of information are clustered so as to be associated with other pieces of information in a particular cluster. 
       SUMMARY OF THE INVENTION 
       [0010]    The present invention is directed to a method for finding clusters in a semantic graph representing evidence, described in narrative text communications constituting a knowledge base, showing that certain pieces of information associated with a scenario are clustered and thus probably relate to each other. The method includes collecting narrative text communications, each formed of a group of words. The groups of words in the narrative text communications are organized into the knowledge base as subject-relation-object triples, e.g., Mario Rossi lives at 2932 University Drive”. The items, identified by groups of words, that are either subjects and/or objects of triples as entities, and to the items, identified by groups of words, that are relations of triples are referred to as relations. The triples are represented by a semantic graph, where each node represents an entity and each segment a relation, and the graph is analyzed using mathematical techniques to recognize groupings or clusters of entities. For example, the method preferably determines how closely related entities in a threat scenario, described in narrative text communications and including multiple targets, are to other entities in the threat scenario. Also, the method determines which events and entities are associated with which targets and shows results in a graph to emphasize how many ways each entity is connected to other entities, especially those in the same cluster. 
         [0011]    Given the semantic graph, which representing the relations among the entities in a knowledge base, the method generates a symmetric weighted adjacency matrix A as follows: wherever there is a segment (link) between two entities i, j, the adjacency matrix will have a positive entry A ij &gt;0 representing the strength of the relation; where there is no segment (link), the adjacency matrix will have a zero entry. The next step is to generate a diagonal degree matrix D by adding up each value of the entries in each row of the adjacency matrix, and placing the sum in the corresponding diagonal position of the diagonal degree matrix. A Laplacian matrix is then produced by subtracting the adjacency matrix from the diagonal degree matrix. As described by spectral graph analysis, important information about the original semantic graph can be deduced by Laplacian matrix. It is well known that the Laplacian matrix associated with a graph is singular, and so it requires some care in order to be inverted. The next step in the method is to take a pseudo inverse of the Laplacian matrix. The pseudo inverse of the Laplacian matrix is interpreted as a measure of the covariance of the entities in the semantic graph. The next step is to remove all values in the pseudo inverse of the Laplacian matrix that are below a threshold, usually picked as 0. This new matrix constitutes a symmetric matrix, and is interpreted as a new adjacency matrix in the “covariance space”. This new adjacency matrix is again be represented as a graph, and the result is a new graph which takes into account not just direct links between entities, but all the paths that connect pairs of entities in the original graph. If all the nodes of the original graph are connected, then the new graph is complete, since there is always a path connecting each pair of entities in the original graph. The new graph is then projected only onto entities of interest, and possible clusters are highlighted. In the examples shown, the new graph is projected onto three types of nodes: people, references and targets, the resulting graph clearly shows clustering. Another Laplacian matrix may be calculated based on the transformed adjacency matrix, and used to perform spectral clustering of the secondary graph as part of the overall method. 
         [0012]    Additional objects, features and advantages of the present invention will become more readily apparent from the following detailed description of preferred embodiments when taken in conjunction with the drawings wherein like reference numerals refer to corresponding parts in the several views. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0013]      FIG. 1  is a flow chart showing a covariance-based clustering algorithm using a modified Laplacian pseudo-inverse matrix according to a preferred embodiment of the invention; 
           [0014]      FIG. 2  shows an example of semantic graph representing a knowledge base of people, places, objects and actions; 
           [0015]      FIG. 3  shows an adjacency matrix generated based on the knowledge base in  FIG. 2 ; 
           [0016]      FIG. 4  shows an example of creating a Laplacian matrix by subtracting the adjacency matrix of  FIG. 3  from a diagonal degree matrix; 
           [0017]      FIG. 5  is a graph showing an adjacency network of a threat scenario knowledge base; 
           [0018]      FIG. 6  is a graph showing the pair-wise connectedness of the adjacency network of  FIG. 5  to show clustering; 
           [0019]      FIG. 7  shows the graph of  FIG. 6  projected onto the entities of actors, weapons and locations, with other entities removed to further emphasize clustering; 
           [0020]      FIG. 8  is a plot of sorted components of an eigenvector associated with the 3 rd  smallest eigenvalues of the transformed adjacency matrix that formed the graph of  FIG. 5 ; 
           [0021]      FIG. 9  is a plot of the result of a clustering algorithm in accordance with the invention applied to the information in the graph shown in  FIG. 5 ; 
           [0022]      FIG. 10  is a plot of the sorted components of the Fiedler vector of the transformed Laplacian matrix of the information in the graph shown in  FIG. 5  according to the prior art; 
           [0023]      FIG. 11  is a plot of the sorted components of the Fiedler vector of the non-negative transformed Laplacian matrix of the information in the graph  FIG. 5  according to the prior art; and 
           [0024]      FIG. 12  is a diagram of a system with computers connected to the interne for implementing the clustering algorithm of  FIG. 1 . 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0025]    With initial reference to  FIG. 1 , there is shown a flow chart depicting a method  10  according to a preferred embodiment of the invention. In order to apply mathematical tools to perform quantitative inference, the evidence must first be represented in a simplified organized manner. To achieve this goal, the evidence is collected as a list of subject-relation-object triples into a knowledge base is shown. The items that are either subjects and/or objects are here referred to as “entities”. 
         [0026]    A first step  20  in method  10  is to collect narrative text reports containing information about a scenario of interest. As noted above, such text reports may be gathered from several sources. For example, computer based communications, such as E-mails, may be intercepted and the contents or a summary of each E-mail may be stored. Telephone intercepts may be translated and also stored, usually as narrative text. Other information may come from police reports describing the results of searches or data on people that have been arrested. In some cases, reports may come from military units that capture people or computers having information of interest. Regardless of the source in each case, a narrative report is produced. 
         [0027]    The evidence, represented as narrative text, is then organized in the knowledge base in the form of a list of triples: “subject-relation-object”. An ontology is developed to specify all the allowable types of triples in the knowledge base, and the narrative text is then organized into triples according to the ontology. The ontology and the list of triples constitute the knowledge base. The items represented as “subject” and/or “attribute” in the triples are referred to as “entities;” and to the items represented as “relation” in the triples as “relations.” At step  30 , the information or facts in the groups of words are represented as subject-relation objection triples, e.g., Mario Rossi lives at 2932 University Drive. At step  40 , the triples are then aggregated to form the knowledge base. 
         [0028]    At step  50 , the knowledge base is represented by a semantic graph, where each node represents an entity and each segment a relation. An example is shown in  FIG. 2  which represents a semantic graph  52  of the knowledge base generated in step  40 . Semantic graph  52  shows entities  61 - 66  arranged to show how entities  61 - 66  are related to one another. The text has been broken down into simple triples including a subject, a predicate and an object. Essentially, the narrative text is coded into a mathematical format.  FIG. 2  includes six entities  61 - 66  which can either be a subject or an object. In this case, semantic graph  52  shows Mario Rossi  61 , Giuseppe Bianchi  62 , Select Gourmet Food  63 , 2932 University Drive  64 ,  1176  Floyd Avenue  65  and a phone number  66 , i.e., (555) 555-####. Semantic graph  52  shows several triplets of subject, predicate and object. Semantic graph  52  is subject to not only mathematical analysis but is also readable by a human observer. By inspection, one can tell that Mario Rossi  61  owns Select Gourmet Food  63 . One can also tell that Mario Rossi  61  owns a phone number  66 , i.e., (555) 555-####, located at 2932 University Drive  64  where he lives. Phone number  66  is located at 1176 Floyd Avenue  65  and Giuseppe Bianchi  62  lives at 2932 University Drive  64 . Once the narrative has been organized, as shown in  FIG. 2 , several mathematical operations and analysis are performed on the data. For example, as described in step  100  of  FIG. 1 , an adjacency matrix is formed, such as adjacency matrix A shown in  FIG. 3 . In adjacency matrix A, all entities  61 - 66  shown in  FIG. 2  have been placed above the first row and before the first column. Where there is a connection between two entities, a positive number is entered in the appropriate location in adjacency matrix A. In the present example a single connection is shown as a one and multiple connections are shown with higher integer numbers. However, any number greater than zero can be used, depending on the weight given to the relations. No connection is shown as a zero or no entry. For example, there are two connections between Mario  61  and 2932 University Drive  64 , thus a “2” is placed in the adjacency matrix at 4,1 and 1,4. Semantic graph  52  shown in  FIG. 2  can also be represented as simply six nodes with lines connected between them. An example of such an adjacency graph formed of nodes and lines is shown in  FIG. 6 , which will be discussed in more detail below. The links between nodes can also be rated, for example, the “2” provided in the adjacency matrix of  FIG. 3 , between Mario  61  and University Drive  64  indicates double the weight of the connection compared to the connection between Mario  61  and Select Gourmet Food  63 . 
         [0029]    While  FIGS. 2 and 3  show a specific semantic graph  52  and a specific adjacency matrix A respectively, such graphs may be more generally described. For example, a semantic graph G=(V,E) is a weighted graph with nodes {V i } i=1, . . . , N , edges {E v } v=1, . . . , M , and weights {W v } v=1, . . . , M , associated with each edge. Then A ε R N×N  would be the weighted symmetric adjacency matrix associated with G calculated at step  100  and defined as: 
         [0030]    A ij =A ji =w v , if there exists an edge E v , with w v ≠0, connecting node V i  to node V j  with i≠j; 
         [0031]    A ij =A ji =0, otherwise. 
         [0032]      FIG. 4  shows a diagonal degree matrix D formed by adding all the values found in each row of adjacency matrix A and placing the sum of the values in a corresponding row of matrix D along its diagonal. The connection weight values between Mario  61  and Foods  63 , University Drive  64  ×2, Floyd Ave  65  and phone number  66  add up to 5, so therefore 5 is placed in the 1,1 position of diagonal degree matrix D and so on. In step  100  of  FIG. 1 , Laplacian matrix L is simply found by subtracting adjacency matrix A from diagonal degree matrix D. 
         [0033]    The next step is to partition a graph into sub-graphs (clusters). In this invention, a cluster S ⊂ G is considered a sub-graph where the nodes are more “connected” to each other than they are to the rest of the nodes in the graph. In statistical data analysis, clusters in the data are characterized by observations having a covariance among each other higher than the covariance with the rest of the data. This statistical interpretation is used to develop the clustering algorithm described in this invention. In particular, a concept of graph-covariance is defined based on the “connectedness” of the nodes in the graph, and then a methodology is provided to partition the graph using the graph-covariance. To achieve this goal in an effective way, the subject method uses variations of a Laplacian matrix and its inverse. 
         [0034]    A pseudo-inverse L′ of a Laplacian matrix L is calculated at step  120  and given an interpretation as the covariance-matrix of a random field Z=(Z 1 , . . . , Z n ), defined at each node V i  of graph G. The random field Z is modeled using a conditional autoregressive (CAR) model, with an adjacency structure defined by adjacency matrix A. In a CAR model, the conditional distribution of the field component Z i  is defined conditionally to the remaining components {Z i :j≠i} as the weighted average: 
         [0000]    
       
         
           
             
               Z 
               i 
             
             = 
             
               
                 
                   
                     ∑ 
                     
                       j 
                       = 
                       1 
                     
                     N 
                   
                    
                   
                       
                   
                    
                   
                     
                       A 
                       ij 
                     
                      
                     
                       Z 
                       j 
                     
                   
                 
                 
                   
                     ∑ 
                     
                       j 
                       = 
                       1 
                     
                     N 
                   
                    
                   
                       
                   
                    
                   
                     A 
                     ij 
                   
                 
               
               + 
               
                 ε 
                 i 
               
             
           
         
       
     
         [0000]    where the error terms are modeled as: 
         [0000]      ε i   ˜N ( 0 ,D ii   −1 ).
 
         [0000]    In other words: the value of field Z at node V i  is equal to the weighted average of the values of Z over all nodes V j  connected to V i , plus an error term that is inverse-proportional to the degree of V i . It can be verified that the joint normal distribution of Z is: 
         [0000]      [ Z]∝e− ½ Z   T     LZ   ,
 
         [0000]    which formally yields L=Σ −1 , with Σ being the covariance matrix of random field Z. Since L is positive semi-definite with a number of 0 eigenvalues equal to the number of connected sub-graphs of G (including G itself), the Moore-Penrose pseudo-inverse L′ is considered as the covariance-matrix of random field Z. 
         [0035]    The connectedness between two nodes in an adjacency graph can also be envisioned by imagining the entire system as a spring mass system where one node may be held stationary and, if the system is excited by moving a second node, the connectedness of that second node to any other node will be the amount that the other node moves given the excitement of the second node. This also relates back to the Moore-Penrose pseudo-inverse L′ because another interpretation of L′ comes from physics or, more precisely, statistical mechanics. Suppose to have a physical system composed of unit-mass particles at each node V i , and linked to each other by springs of elastic constant k v =w v  at each edge E v . Let Z=(Z 1 , . . . ,Z n ) be the field of the amplitudes of oscillation of the particles in the system. The potential energy of the system can be written as 
         [0000]    
       
         
           
             
               U 
                
               
                 ( 
                 Z 
                 ) 
               
             
             = 
             
               
                 
                   1 
                   4 
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       , 
                       
                         j 
                         = 
                         1 
                       
                     
                     N 
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         ( 
                         
                           
                             Z 
                             i 
                           
                           - 
                           
                             Z 
                             j 
                           
                         
                         ) 
                       
                       2 
                     
                      
                     
                       A 
                       ij 
                     
                   
                 
               
               = 
               
                 
                   1 
                   2 
                 
                  
                 
                   
                     Z 
                     T 
                   
                    
                   
                     ( 
                     
                       D 
                       - 
                       A 
                     
                     ) 
                   
                 
                  
                 Z 
               
             
           
         
       
     
         [0000]    and, disregarding the kinetic term, the classical partition function of system is 
         [0000]        W=∫e− ½ Z   T     LZ     dZ.  
 
         [0000]    Therefore, the pseudo inverse of L is interpreted as the covariance-matrix of the amplitudes of oscillation of the particles of a spring-network defined by weighted adjacency matrix A. 
         [0036]    At step  140 , the clustering algorithm of the current invention starts by representing the elements of the pseudo-inverse L′ of the Laplacian which are above or equal a given threshold usually set equal to zero, as the adjacency matrix of a new graph, which is displayed at step  160 . Preferably all nodes that are not of the type of interest are removed at step  180 . The algorithm then tries to find clusters into this new graph at step  200  as described more fully below. Without loss of generality, suppose G to be a connected graph. If a graph G contains non-connected sub-graphs, then the clustering algorithm should be applied to each connected sub-graph. Notice the partition of a graph into connected sub-graphs can be solved in linear time using either ‘breadth-first search’ or ‘depth-first search’. The covariance clustering algorithm comprises the following steps:
       1) Given a undirected connected graph G, build the weighted adjacency matrix A, the Laplacian matrix L, and calculate the pseudo-inverse L′;   2) Construct a “transformed” adjacency matrix Â ij (η)=max(L′ ij ,η), where η is a real number referred to as ‘threshold’;   3) Partition at step  200  graph G based on “transformed” graph Ĝ(η) associated with adjacency matrix Â ij (η) using the transformed Laplacian {circumflex over (L)}={circumflex over (D)}−Â, where {circumflex over (D)} is the degree matrix defined as: {circumflex over (D)} ii =Σ j=1   N Â ij ; {circumflex over (D)} ij =0 for every i≠j.       
 
         [0040]    A good choice for threshold η is the average of the elements of L′, that is, 
         [0000]    
       
         
           
             
               η 
               0 
             
             = 
             
               
                 1 
                 
                   n 
                   2 
                 
               
                
               
                 
                   ∑ 
                   
                     i 
                     , 
                     j 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     L 
                     ij 
                     ′ 
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    Considering that, in a connected graph, the constant eigenvector u=(1,1, . . . , 1) is associated with the 0 eigenvalue, then 
         [0000]    
       
         
           
             
               
                 ∑ 
                 
                   i 
                   , 
                   j 
                 
               
                
               
                   
               
                
               
                 L 
                 ij 
                 ′ 
               
             
             = 
             
               
                 
                   ∑ 
                   i 
                 
                  
                 
                     
                 
                  
                 
                   
                     ( 
                     
                       
                         L 
                         ′ 
                       
                        
                       u 
                     
                     ) 
                   
                   i 
                 
               
               = 
               0 
             
           
         
       
     
         [0000]    and therefore η 0 =0. 
         [0041]    Another feature of the invention is the possibility to “prune”, for example, at step  180 , the new graph in order to keep only the entities that are of interest in the analysis. Consider, for example, a graph G=(V, E) containing only two types of nodes: ‘Person’ and ‘City’. Suppose that nodes of type ‘Person’ are connected only to nodes of type ‘City’. Moreover, suppose that analysts are interested only in clustering nodes of type ‘Person’. If the sub-graph G 1  ⊂ G containing only ‘Person’-type nodes is considered, then G 1  will have no edges (each node is disconnected) and therefore the sub-graph G 1  will provide no information about the relationships among the ‘Person’-type nodes in the graph. However, if the matrix Â is built from the pseudo inverse of the Laplacian, and the graph Ĝ associated with Â is considered in the covariance-space, each node of type ‘Person’ will be connected to every other nodes of type ‘Person’ through paths in the original graph G. The sub-graph G 1  ⊂Ĝ containing only ‘Person’-type nodes is used to find clusters of persons using the spectrum of A 1 , which is the sub-matrix of Â containing only rows and columns associated with ‘Person’-type nodes. Â 1  is called the projection of Â onto the ‘Person’-type nodes. Projecting A onto the nodes-of-interest can improve the classification power of the clustering algorithm, as the following example shows. 
         [0042]      FIG. 5  represents an adjacency graph; in this case, a knowledge base was built using a Sign of the Crescent case-study given at the Joint Military Intelligence College, Defense Intelligence Agency. A plot  300  of the adjacency graph using the force-directed layout algorithm of the Social Network Analysis by Carter Butts, SNA R-package is shown in  FIG. 5  and clusters are not distinguishable. As described above, each node represents an entity and the segment between each node represents the fact that the nodes are connected somehow. In general, the goal of the analysis is to find out how many different ways each node is connected to any other given node. Essentially, the number of connections between one node and another node must be counted. Two nodes that are highly connected have numerous possible ways of traveling between them, while two nodes that are connected would have fewer such paths. The connectedness between two nodes can also be envisioned by imagining the entire system as a spring mass system where one node may be held stationary and, if the system is excited by moving a second node, the connectedness to that second node given any other node will be the amount that the other node moves given the excitement of the second node. A plot  310  of the graph Ĝ(0), associated with the transformed adjacency matrix Â with a threshold η=0, using the force-directed layout algorithm of the SNA R-package is shown in  FIG. 6  showing the formation of clusters with a simple visual analysis. Since the interest is in finding the terrorist attacks, Â is projected onto nodes of type: people, weapons, targets. A plot of the corresponding projected graph Ĝ i  is shown in  FIG. 7 , the nodes representing the entities (persons, weapons, targets) involved in the three different attacks. The covariance-clustering algorithm, together with a typed-projection, completely classified the entities that took part in the three different attacks  320 ,  330 ,  340 . The clusters in Ĝ 1  are identified by using the eigenvectors of Â 1  associated with the smallest non-zero eigenvalues. A plot of the sorted components of the eigenvector associated with the 3 rd  smallest eigenvalue of Â 1  is shown in  FIG. 8  and clearly indicates the presence of three clusters. Finally, a plot of the sorted components of the Fiedler vector of the non-negative transformed Laplacian matrix {circumflex over (L)} is shown in  FIG. 10 . Three clusters associated with the three terrorist attacks are shown separated by the two large gaps around index=50 and index=100. The last plot is the result of the clustering algorithm described in this invention with the suggested threshold η=0. 
         [0043]    As shown in  FIG. 12 , a system for implementing the method shown in  FIG. 1  in accordance with a preferred embodiment of the present invention includes an analyst&#39;s computer system  810  which can be connected to one or more other computer systems  812  over an electronic communications link such as the internet  814 . As illustrated in  FIG. 12 , analyst&#39;s computer system  810  includes an input-output unit  820  for transmitting and receiving digital information to or from the internet  814 . Likewise, each computer system  812  is also set up to contact internet  814  through an input-output unit  845  and preferably hosts websites  816  in a memory  818 . Computer  810  typically has a monitor  854 , a central processing unit  855 , some type of memory  856  and a keyboard  857 . Typically, when in use, analyst&#39;s computer operating system, such as Macintosh®, Unix® or Windows® which controls the basic operations of the computing machine. Additionally, specialized applications, such as a web browser, would be used to interpret the various protocols of internet  814  into an understandable interface for a computer user, namely the analyst. The knowledge base is preferably stored in memory  856  as semantic graph  52  or in other formats. Plot  310  of graph Ĝ(0) or other graphs developed with the clustering method are preferably displayed on monitor  854 . Various specific pieces of software used to complete the method steps of algorithm 10 shown in  FIG. 1  reside in memory  856 . For example the force-directed layout algorithm of the Social Network Analysis by Carter Butts, SNA R-package is preferably located in memory  856 . 
         [0044]    Based on the above, it should be readily apparent the method of the present invention provides an efficient way to identify clusters in a knowledge base. The “transformed” graph Ĝ can be viewed as a covariance representation of the original graph G. In G the relationships among the nodes are induced by the paths in the original graph G. Moreover, since G is usually dense (in fact, G is complete whenever G is connected), Ĝ can be projected onto subsets of nodes of type of interest (e.g., persons, weapons, and targets, in the example given above), and improve the discrimination power of the algorithm. 
         [0045]    Although described with reference to preferred embodiments of the invention, it should be readily understood that various changes and/or modifications can be made to the invention without departing from the spirit thereof. For example, The covariance clustering algorithm may be applied to any adjacency graph, not just one created from a threat scenario, regardless of what data is used to create the graph. For example, the algorithm can be used to analyze the World Wide Web, using a graph where each node is a web page and each segment is a link between pages. In general, the invention is only intended to be limited by the scope of the following claims.