SYSTEM AND METHOD FOR SUPERVISED NETWORK CLUSTERING

• US 20140047091A1
• Filed: 09/11/2012
• Published: 02/13/2014
• 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.
• Granted Patent: US 10,135,723 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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;

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 apparatus of claim 1, wherein a random walk process is used to define the densities.

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 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 1, wherein smaller components having a size less than the user-defined threshold are merged with larger components.

7. The apparatus of claim 6, wherein each smaller component is merged to the component with which it has a largest number of connections.

8. The apparatus of claim 4, wherein said clustering is iterative and continues until no further merging of small clusters occurs.

9. The apparatus of claim 8, wherein a threshold for an iteration comprises an average density over all remaining nodes.

10. The apparatus of claim 1, wherein said network comprises a group of entities connected by links.

11. 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;

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.

12. The server of claim 11, wherein said clusters are extracted based on using a threshold on said densities.

13. The server of claim 12, further comprising merging smaller clusters with sizes below a user-defined threshold.

14. The server of claim 12, wherein said cluster extraction comprises an iterative process.

15. The server of claim 14, wherein said threshold initially comprises an average density of said network,

16. A computer, comprising:

a processor; and

a memory device, said memory device storing a set of computer-readable instructions for said CPU to execute a method of clustering, said method comprising;

calculating a density associated with each of a plurality of nodes on a network, as executed by a processor on a computer having access to said network, said network defined by a group of entities connected by links; and

defining clusters of nodes in said network based on said densities.

17. The computer of claim 16, wherein said densities are calculated as a random-walk-based probability for each said node on said network corresponding to a page-rank computation.

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

19. The computer of claim 16, wherein said defining of clusters comprises an iterative process until substantially all nodes of said plurality of nodes are included in a cluster.

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