Efficient Method for Clustering Nodes

Abstract

Methods and computer storage media for clustering nodes are provided. An input file is received that is comprised of primary nodes, secondary nodes and metrics that relate to the association between the primary nodes and the secondary nodes. Upon receiving the input file, the input file may be abridged to reduce the number of nodes contained in the input file. The unique initial primary nodes may then be clustered with their associated secondary node. The clusters containing the unique initial primary nodes may then be replaced if a subsequent related cluster satisfies a pre-defined condition. In some embodiments, multiple clusters may then be merged until the cluster size reaches a pre-defined size. In some embodiments, the input file is may be cleaned and sorted prior to being abridged.

1 . One or more computer storage media having computer-executable instructions embodied thereon that, when executed, perform a method for clustering nodes, the method comprising:
 receiving an input file comprised of a plurality of primary nodes, a plurality of secondary nodes, and a plurality of metrics, wherein each of the plurality of metrics describes a relationship between one of the plurality of primary nodes and one of the plurality of secondary nodes;   abridging the input file to generate an abridged file that is comprised of:
 (1) a plurality of abridged primary nodes, 
 (2) a plurality of abridged secondary nodes, and 
 (3) a plurality of abridged metrics; and 
   merging a first abridged primary node of the plurality of abridged primary nodes with a first abridged secondary node of the plurality of abridged secondary nodes to form a first cluster.   
     
     
         2 . The computer storage media of  claim 1 , wherein the method further comprises replacing the first abridged secondary node in the first cluster with a second abridged secondary node of the plurality of abridged secondary nodes. 
     
     
         3 . The computer storage media of  claim 2 , wherein the first abridged secondary node is replaced with the second abridged secondary node based on a replacement condition. 
     
     
         4 . The computer storage media of  claim 1 , wherein the method further comprises merging the first cluster with a second cluster to create a resulting cluster, wherein the abridged primary node of the first cluster is comparable to an abridged primary node of the second cluster. 
     
     
         5 . The computer storage media of  claim 4 , wherein the first cluster is merged with the second cluster when the first cluster is comprised of a defined number of nodes. 
     
     
         6 . The computer storage media of  claim 4 , wherein the first cluster is merged with the second cluster when the first cluster contains less than a defined number of nodes. 
     
     
         7 . The computer storage media of  claim 4 , wherein the plurality of abridged metrics represent a strength of a relationship between one of the plurality of abridged primary nodes and one of the plurality of abridged secondary nodes. 
     
     
         8 . The computer storage media of  claim 4 , wherein the method further comprises:
 determining the first abridged primary node is not an initial occurrence of the first abridged primary node; and   identifying the second cluster having a comparable abridged primary node to the abridged primary node of the first cluster.   
     
     
         9 . The computer storage media of  claim 1 , wherein the method further comprises removing unreliable data from the input file. 
     
     
         10 . The computer storage media of  claim 1 , wherein the method further comprises sorting the input file by the plurality of metrics. 
     
     
         11 . The computer storage media of  claim 1 , wherein abridging the input file is comprised of reducing a number of the plurality of primary nodes to a pre-defined maximum number. 
     
     
         12 . The computer storage media of  claim 1 , wherein abridging the input file is comprised of reducing a number of the plurality of secondary nodes to a pre-defined maximum number. 
     
     
         13 . The computer storage media of  claim 1 , wherein abridging the input file is comprised of reducing a number of the plurality of metrics to a pre-defined maximum number. 
     
     
         14 . The computer storage media of  claim 1 , wherein the input file is derived from either a social networking database or an advertising database. 
     
     
         15 . A method for clustering nodes in a computing environment having a processor and memory, the method comprising:
 receiving an input file comprised of a plurality of primary nodes, a plurality of secondary nodes, and a plurality of metrics, wherein each of the plurality of metrics describes a relationship between one of the plurality of primary nodes and one of the plurality of secondary nodes;   abridging, utilizing the processor and memory, the input file to generate an abridged file that is comprised of:
 (1) a plurality of abridged primary nodes, 
 (2) a plurality of abridged secondary nodes, and 
 (3) a plurality of abridged metrics; and 
   merging a first abridged primary node of the plurality of abridged primary nodes with a first abridged secondary node of the plurality of abridged secondary nodes to form a first cluster; and   replacing the first abridged secondary node in the first cluster with a second abridged secondary node of the plurality of abridged secondary nodes.   
     
     
         16 . The method of  claim 15 , wherein the first abridged secondary node is replaced with the second abridged secondary node based on a replacement condition associated with at least one of the plurality of abridged metrics. 
     
     
         17 . The method of  claim 15 , wherein the method further comprises merging the first cluster with a second cluster to create a resulting cluster, wherein the abridged primary node of the first cluster is comparable to an abridged primary node of the second cluster. 
     
     
         18 . The method of  claim 15 , wherein abridging the input file is comprised of reducing, to a predefined number, at least one of:
 1) the plurality of primary nodes,   2) the plurality of secondary nodes, or   3) the plurality of metrics.   
     
     
         19 . The method of  claim 15 , wherein the input file is derived from either a social networking source or an advertising source. 
     
     
         20 . A system for clustering nodes in a computing environment having a processor and memory, the system comprising:
 a receiving component functional to receive an input file comprised of a plurality of primary nodes, a plurality of secondary nodes, and a plurality of metrics, wherein each of the plurality of metrics describes a relationship between one of the plurality of primary nodes and one of the plurality of secondary nodes;   an abridging component functional to abridge the input file to generate an abridged file that is comprised of:
 (1) a plurality of abridged primary nodes, 
 (2) a plurality of abridged secondary nodes, and 
 (3) a plurality of abridged metrics; and 
   a merging component functional to merge a first abridged primary node of the plurality of abridged primary nodes with a first abridged secondary node of the plurality of abridged secondary nodes to form a first cluster.