METHOD OF ANALYZING A GRAPH WITH A COVARIANCE-BASED CLUSTERING ALGORITHM USING A MODIFIED LAPLACIAN PSEUDO-INVERSE MATRIX

摘要

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