Role grouping
Techniques to assign nodes in a network to groups of nodes includes grouping nodes on a network into groups based on host connection set data by identifying bi-connected components in the host connection set data; and merging groups with similar connection habits as determined by examining the host connection set data into larger groups.
1. A computer implemented method to assign nodes in a network to groups of nodes, comprising:
observing connection patterns between nodes in the network;
identifying nodes with similar connection patterns in the network, wherein the similar connection patterns are based on regular communication with common network end nodes;
generating a connectivity graph based on observed connection patterns between nodes, wherein, in the connectivity graph, a vertex denotes a node, and an edge between vertices denotes a one-hop connectivity between the corresponding nodes;
grouping the identified nodes into groups based on the connectivity graph; and
merging a first group and a second group into a larger group in response to:
determining that a similarity measure between the first group and the second group exceeds a user-defined threshold, wherein the similarity measure is based on connection patterns from the first group and the second group, and
determining that a first average number of connected host pairs in the first group is within a pre-determined percentage of a second average number of connected host pairs in the second group.
2. The method of claim 1 , wherein said grouping involves identifying bi-connected components, wherein a bi-connected component is a connected component in which any two edges of the component lie in a simple cycle.
3. The method of claim 1 , wherein said grouping includes:
assigning a unique integer identifier to each group.
4. The method of claim 1 , wherein said merging further comprises:
building a k-neighborhood graph from the connectivity graph;
removing group nodes from the connectivity graph; and
generating all bi-connected components in the k-neighborhood graph.
5. The method of claim 4 , wherein for each bi-connected component in the all bi-connected components, forming the groups further comprises:
replacing the nodes in the connectivity graph by a new group node of the replaced nodes; and
labeling a group by a unique identifier and by a degree of similarity between the groups.
6. The method of claim 5 further comprising:
iteratively examining the connection graph until no ungrouped node remains or the degree of similarity between groups is zero.
7. The method of claim 1 , wherein said grouping further comprises:
constructing a k-neighborhood graph to identify bi-connected components from the connectivity graph; and
responsive to a set of nodes placed into a group, assigning nodes in one group to a new group by removing vertices representing the nodes from the connectivity graph and replacing the vertices by one vertex representing the entire group.
8. The method of claim 1 , wherein said grouping is repeated until the groups are large enough that no new groups are to be assigned.
9. The method of claim 1 , wherein for each pair of two groups, G 1 and G 2 , the merging the groups comprises:
appending a triple (G 1 , G 2 , s) to a list of node edges, where s represents a degree of similarity between the two groups, G 1 and G 2 .
10. The method of claim 9 , wherein said merging further comprises:
sorting the list of edges based on their s-values in descending order.
11. The method of claim 10 , wherein said merging further comprises:
forming a new group based on G 1 and G 2 and assigning a number of connection pairs to a host in group G, which is a union of G 1 and G 2 .
12. An apparatus comprising:
a processor;
a memory; and
an observation mechanism configured to observe connection patterns between nodes in a network;
an identification mechanism configured to identify nodes with similar connection patterns in the network, wherein the similar connection patterns are based on regular communication with common network end nodes;
a generating mechanism configured to generate a connectivity graph based on observed connection patterns between nodes, wherein, in the connectivity graph, a vertex denotes a node, and an edge between vertices denotes a one-hop connectivity between the corresponding nodes;
a grouping mechanism configured to group the identified nodes into groups based on the connectivity graph; and
a merging mechanism configured to merge a first group and a second group into a larger group in response to:
determining that a similarity measure between the first group and the second group exceeds a user-defined threshold, wherein the similarity measure is based on connection patterns from the first group and the second group, and
determining that a first average number of connected host pairs in the first group is within a pre-determined percentage of a second average number of connected host pairs in the second group.
13. The apparatus of claim 12 , wherein the grouping mechanism is further configured to identify bi-connected components, wherein a bi-connected component is a connected component in which any two edges of the component lie in a simple cycle.
14. The apparatus of claim 12 wherein the grouping mechanism is further configured to:
assign a unique integer identifier to each group.
15. The apparatus of claim 12 , wherein the merging mechanism is further configured to:
build a k-neighborhood graph from the connectivity graph;
remove group nodes from the connectivity graph; and
generate all bi-connected components in the k-neighborhood graph.
16. The apparatus of claim 15 , wherein for each bi-connected component the group forming mechanism is configured to:
replace the nodes in the connectivity graph by a new group node of the replaced nodes; and
label a group by a unique identifier and by a degree of similarity between the groups.
17. The apparatus of claim 16 further comprising instructions to:
iteratively examining the connection graph until no ungrouped node remains or the degree of similarity between groups is zero.
18. The apparatus of claim 12 , wherein the grouping mechanism is further configured to:
construct a k-neighborhood graph to identify bi-connected components in the connectivity graph; and
responsive to a set of nodes being placed into a group, assign nodes in one group to a new group by removing vertices representing the nodes from the connectivity graph and replacing the vertices by one vertex representing the entire group.
19. The apparatus of claim 12 , wherein the grouping mechanism is configured to repeat until the groups are large enough that no new groups are to be assigned.
20. A computer program product residing on a non-transitory computer readable medium for assigning nodes in a network to groups of nodes comprising instructions, which when executed by a computer, cause the computer to:
observe connection patterns between nodes in the network;
identify nodes with similar connection patterns in the network, wherein the similar connection patterns are based on regular communication with common network end nodes;
generate a connectivity graph based on observed connection patterns between nodes, wherein, in the connectivity graph, a vertex denotes a node, and an edge between vertices denotes a one-hop connectivity between the corresponding nodes;
group the identified nodes into groups based on the connectivity graph; and
merge a first group and a second group into a larger group in response to:
determining that a similarity measure between the first group and the second group exceeds a user-defined threshold, wherein the similarity measure is based on connection patterns from the first group and the second group, and
determining that a first average number of connected host pairs in the first group is within a pre-determined percentage of a second average number of connected host pairs in the second group.
21. The computer program product of claim 20 , wherein said instructions for causing the computer to group the identified nodes into groups include instructions to identify bi-connected components, wherein a bi-connected component is a connected component in which any two edges of the component lie in a simple cycle.
22. The computer program product of claim 20 , wherein said instructions for causing the computer to group the identified nodes into groups comprise instructions to:
assign a unique integer identifier to each group.
23. The computer program product of claim 20 , wherein said instructions to merge further comprise instructions to:
build a k-neighborhood graph from the connectivity graph;
remove group nodes from the connectivity graph; and
generate all bi-connected components in the k-neighborhood graph.
24. The computer program product of claim 23 , wherein, for each bi-connected component in the all bi-connected components, said instructions for causing the computer to group the identified nodes into groups further comprise instructions to:
replace the nodes in the connectivity graph by a new group node of the replaced nodes; and
label a group by a unique identifier and by a degree of similarity between the groups.
25. The computer program product of claim 24 further comprising instructions to:
iteratively examining the connection graph until no ungrouped node remains or the degree of similarity between groups is zero.
26. The computer program product of claim 20 , wherein said instructions for causing the computer to group the identified nodes into groups further comprise instructions to:
construct a k-neighborhood graph to identify bi-connected components in the connectivity graph; and
responsive to a set of nodes being placed into a group, assign nodes in one group to a new group by removing vertices representing the nodes from the connectivity graph and replacing the vertices by one vertex representing the entire group.
27. The computer program product of claim 20 , wherein said instructions for causing the computer to group the identified nodes into groups repeat until the groups are large enough that no new groups are to be assigned.