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.
Please help me write a proper abstract based on the patent claims. CLAIM: 1. A computer implemented method for analyzing a graph, representing messages including groups of words that describe facts about entities, with a covariance-base clustering algorithm for determining how closely related the entities are to each other, the method comprising: collecting the messages; storing the facts into a knowledge base; representing the knowledge base as a semantic graph; building a weighted, symmetric, adjacency matrix from the semantic graph; calculating a Laplacian matrix from the adjacency matrix; calculating a Moore-Penrose pseudo-inverse of the Laplacian matrix; building a transformed adjacency matrix equal to the pseudo-inverse of the Laplacian matrix with all entries, which are greater than or equal to a chosen threshold; and performing a spectral analysis on the transformed adjacency matrix to identify clustering in the semantic graph. 2. The method according to claim 1, further comprising displaying the transformed adjacency matrix as a transformed graph on a display screen and showing how closely related the entities are to each other. 3. The method according to claim 2, wherein performing the spectral analysis includes determining which entities are clustered together on the transformed graph by separating sub-graphs characterized by a within-cluster covariance larger than an across-clusters covariance. 4. The method according to claim 1, wherein storing the facts into a knowledge base includes creating a list of subject-relation-object triples, wherein each of the groups of words used as a subject or an object in each triple constitutes one of the entities and every group of words used as a relation in a triple defines a relationship between the subject and object. 5. The method according to claim 4, wherein representing the knowledge base as a semantic graph includes creating said semantic graph with nodes and edges, while representing one of the entities with each node and representing a relationship between two of the entities with each edge. 6. The method according to claim 5, wherein building a weighted, symmetric, adjacency matrix includes associating a weight to each edge in the graph representing a strength of a relationship between each pair of entities. 7. The method according to claim 1, further comprising setting the chosen threshold equal to an average of the entries of the pseudo-inverse of the Laplacian matrix. 8. The method according to claim 1, wherein collecting the messages includes collecting computer based communications and producing a narrative report. 9. The method according to claim 8 wherein producing a narrative report includes summarizing emails. 10. The method according to claim 8, wherein the communications are webpages. 11. The method according to claim 1, wherein collecting the messages includes summarizing conversations in a text format. 12. The method according to claim 1, wherein the messages describe a threat scenario. 13. A method for determining 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 and for determining which entities are associated with which targets, the method comprising: collecting narrative text communications, including facts or evidence, each communication including a group of words, regarding the threat scenario; storing the facts into a knowledge base as a list of subject-relation-object triples with the subject or object of each triple representing one of the entities, and representing the knowledge base as a semantic graph, with nodes representing the entities and edges representing the relations; building an adjacency matrix; calculating a Laplacian matrix from the adjacency matrix; building a transformed adjacency matrix equal to a pseudo-inverse of the Laplacian matrix; and performing a spectral analysis on the transformed adjacency matrix to identify clustering in the semantic graph. 14. The method according to claim 13, wherein building an adjacency matrix comprises building a weighted, symmetric, adjacency matrix associating a weight to each edge in the graph measuring a strength of the relation between each pair of entities. 15. The method according to claim 14 further comprising: calculating a Moore-Penrose pseudo-inverse of the Laplacian matrix prior to building the transformed adjacency matrix; building the transformed adjacency matrix with all entries in the adjacency matrix that are greater than or equal to a chosen threshold set equal to zero setting the threshold equal to an average of the entries of the pseudo-inverse of the Laplacian matrix; displaying a transformed graph associated with the transformed adjacency matrix; and calculating a transformed Laplacian associated with the transformed adjacency matrix. 16. The method according to claim 1 further comprising projecting the transformed adjacency matrix onto a subset of entities of interests. 17. The method according to claim 15 further comprising projecting the transformed adjacency matrix onto a subset of entities of interests.