System and method for supervised network clustering

• US 10,135,723 B2
• Filed: 09/11/2012
• Issued: 11/20/2018
• Est. Priority Date: 08/10/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C.
• Primary Examiner(s): Christensen, Scott B
• Assistant Examiner(s): Do, Lam T
• Application Number:
  US13/610,092
• Publication Number:
  US 20140047091A1
• Time in Patent Office: 2,261 Days
• Field of Search: None
• CPC Class Codes: H04L 45/46 Cluster building

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.

Claims

1. An apparatus, comprising:

a processor; and

a memory device, said memory device storing therein a set of machine-readable instructions permitting said processor to execute 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 node labels comprising a set of keywords describing each node;

using said node labels to calculate a density for each node by using a random walk process as a measure of probability of traversing from said node to adjacent nodes in said network, to define densities associated with said nodes; and

iteratively extracting node cluster components from the network as network clusters, based on using thresholds on node densities, wherein a threshold for an iteration comprises an average density over all remaining nodes,

wherein said threshold is user-defined and smaller-cluster components having a size less than a user-defined threshold value are merged with larger cluster components, wherein each smaller cluster component is merged to a cluster component with which it has a largest number of connections, the merging thereby reducing a noise in the network clustering and adapting the network clustering to local densities in said network.

2. The apparatus of claim 1, wherein a higher probability is interpreted as indicative that said node more likely is associated with a network cluster.

3. The apparatus of claim 2, wherein a restart vector associated with the random walk is defined on a basis of node labels.

4. The apparatus of claim 1, wherein density-connected nodes above a given threshold are determined as initial cluster components.

5. The apparatus 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 apparatus of claim 4, wherein said clustering is iterative and continues until no further merging of small clusters occurs.

7. The apparatus of claim 1, wherein said node labels are associated with different classes, wherein said random walk process includes a parameter that affects said random walk process, and wherein said random walk process parameter is selectively associated with different values for different classes of node labels, to thereby provide a supervision mechanism to said network clustering.

8. The apparatus of claim 1, wherein said random walk process derives a probability value based on a PageRank Algorithm.

9. A server comprising:

an input port to receive information concerning nodes on a network; and

a processor, wherein said processor;

receives, via said input port, and reads node labels from a plurality of nodes on the network, said network defined by a group of entities connected by links, said node labels comprising a set of keywords describing each node;

calculates a random-walk-based probability for each said node on said network, to define densities associated with said nodes; and

defines clusters of nodes in said network based on said densities,

wherein said clusters are extracted based on using a threshold value of said densities, wherein said threshold value initially comprises an average density of said network,

wherein each node in said network is placed into one of said clusters, and

wherein said cluster extraction comprises an iterative process, wherein said threshold value for each said iteration comprises an average density of remaining nodes across said network during that iteration;

merging smaller clusters with sizes below a user-defined threshold value, the merging thereby reducing a noise in the network clustering and adapting the network clustering to local densities in said network.

10. The server of claim 9, further comprising merging smaller clusters with sizes below a user-defined threshold value.

11. A computer, comprising:

A processor having access to a network, said network defined by a group of entities interconnected by links; and

a memory device, said memory device storing a set of computer-readable instructions for said processor to execute an iterative method of clustering of said entities, said method comprising;

calculating a density associated with each said entity on said network, as executed by said processor; and

defining clusters of entities in said network based on said densities, wherein further defining comprise a cluster extraction based on using a threshold value of said densities, wherein said threshold value initially comprises an average density of said network,

wherein said densities are calculated as a random-walk-based probability for each said node on said network, corresponding to a PageRank computation on node labels of said nodes, said node labels comprising a set of keywords describing each node, and

wherein said defining of clusters comprises an iterative process until all nodes of said plurality of nodes are included in a cluster of a predefined minimum cluster size, wherein said threshold value for each said iteration comprises an average density of remaining nodes across said network during that iteration;

merging smaller clusters with sizes below a user-defined threshold value, the merging thereby reducing a noise in the network clustering and adapting the network clustering to local densities in said network.

12. The computer of claim 11, wherein inputs to said processor for calculating said densities comprise links and labels for said nodes.

13. The computer of claim 11, wherein said clusters are merged, based upon a user-defined threshold.