System and method for supervised network clustering

Abstract

A method (and system) for supervised network clustering includes receiving and reading node labels from a plurality of nodes on a network, as executed by a processor on a computer having access to the network, the network defined as a group of entities interconnected by links. The node labels are used to define densities associated with the nodes. Node components are extracted from the network, based on using thresholds on densities. Smaller components having a size below a user-defined threshold are merged.

What is claimed is: 
     
         1 . A method of supervised network clustering, said method comprising:
 receiving and reading node labels from a plurality of nodes on a network, as executed by a processor on a computer having access to said network, said network being defined as a group of entities interconnected by links;   using said node labels to define densities associated with said nodes;   extracting node components from the network, based on using thresholds on densities; and   merging smaller components having a size below a user-defined threshold.   
     
     
         2 . The method of  claim 1 , wherein a random walk process is used to define the densities. 
     
     
         3 . The method of  claim 2 , wherein a restart vector associated with the random walk is defined on a basis of node labels. 
     
     
         4 . The method of  claim 1 , wherein density-connected nodes above a given threshold are determined as initial components. 
     
     
         5 . The method of  claim 4 , wherein the density-connected nodes are defined as nodes between a path that exists in which all nodes have densities greater than the threshold. 
     
     
         6 . The method of  claim 1 , wherein smaller components having a size less than the user-defined threshold are merged with larger components. 
     
     
         7 . The method of  claim 6 , wherein each smaller component is merged to the component with which it has a largest number of connections. 
     
     
         8 . The method of  claim 4 , wherein said clustering is iterative and continues until no further merging of small clusters occurs. 
     
     
         9 . The method of  claim 8 , wherein a threshold for an iteration comprises an average density over all remaining nodes. 
     
     
         10 . The method of  claim 1 , as embodied as a set of computer-readable instructions tangibly embodied on a non-transitory storage medium. 
     
     
         11 . A method of clustering, said method comprising:
 receiving and reading node labels from a plurality of nodes on a network, as executed by a processor on a computer having access to said network, said network defined as a group of entities interconnected by links;   calculating a random-walk-based probability for each said node on said network, to define densities associated with said nodes; and   defining clusters of nodes in said network based on said densities.   
     
     
         12 . The method of  claim 11 , wherein said clusters are extracted based on using a threshold on said densities. 
     
     
         13 . The method of  claim 12 , further comprising merging smaller clusters with sizes below a user-defined threshold. 
     
     
         14 . The method of  claim 12 , wherein said cluster extraction comprises an iterative process. 
     
     
         15 . The method of  claim 14 , wherein said threshold initially comprises an average density of said network. 
     
     
         16 . The method of  claim 11 , as embodied as a set of computer-readable instructions tangibly embodied on a non-transitory storage medium. 
     
     
         17 . The method of  claim 16 , wherein said non-transitory storage medium comprises one of:
 a Random Access Memory (RAM) device of a computer, as storing said computer-readable instructions for a program currently executing on said computer;   a Read Only Memory (ROM) device of a computer, as storing said computer-readable instructions for a program that can selectively be executed by said computer;   a standalone memory device storing said computer-readable instructions for a program that can selectively be uploaded onto a memory device in a computer; and   a memory device associated with a computer on the network, as storing said computer-readable instructions for a program that can selectively be downloaded to a memory device of another computer on said network.   
     
     
         18 . A method if clustering, said method comprising:
 calculating a density associated with a plurality of nodes on a network, as executed by a processor on a computer having access to said network, said network defined as a group of entities interconnected by links; and   defining clusters of nodes in said network based on said densities.   
     
     
         19 . The method of  claim 18 , wherein said densities are calculated as a random-walk-based probability for each said node on said network. 
     
     
         20 . The method of  claim 18 , further comprising merging smaller cluster components having a size below a user-defined threshold.