Determining user communities in communication networks

• US 9,491,055 B1
• Filed: 04/21/2010
• Issued: 11/08/2016
• Est. Priority Date: 04/21/2010
• Status: Active Grant

• Current Assignee: T-Mobile Innovations LLC (Deutsche Telekom AG)
• Original Assignee: Sprint Communications Company LP (Deutsche Telekom AG)
• Inventors: Schneider, James Christopher, Sridharan, Ashwin, Seshadri, Mukund, Prakash, Bodicherla Aditya, Faloutsos, Christos, Machiraju, Sridhar
• Primary Examiner(s): Tiv, Backhean
• Application Number:
  US12/764,730
• Time in Patent Office: 2,393 Days
• Field of Search: 709224-226, 705/319
• US Class Current: 1/1
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

What is disclosed is a method of operating a communication network, where the communication network comprises a set of users. The method includes obtaining usage activity for each of the users of the set and processing the usage activity to determine connectivity information between individual ones of the users of the set. The method also includes processing the connectivity information to determine users of the set with similar connectivity, and processing the users of the set with similar connectivity to identify a community of users within the users of the set with similar connectivity. The method also includes monitoring at least one of the users in the community to determine if action is needed for at least another one of the users in the community.

Claims

1. A method of operating a processing node for a communication network having a set of users, the method comprising:

in the processing node, monitoring usage activity for the set of users of the communication network;

in the processing node, processing the usage activity for the set of users to generate an adjacency matrix comprising connectivity information between individual ones of the users of the set;

in the processing node, processing the adjacency matrix to determine eigenvectors;

in the processing node, if at least two of the eigenvectors are perpendicular, then processing the eigenvectors to determine a first user node of the set of users with a highest magnitude along a first eigenvector of the eigenvectors, and including the first user node in a provisional user community having shared connectivity;

in the processing node, identifying additional user nodes of the set of users having high magnitudes along the first eigenvector and that share connectivity with at least one other user node already included in the provisional user community, and including the additional user nodes in the provisional user community until modularity of the provisional user community decreases;

in the processing node, processing the provisional user community to identify and exclude incorrectly identified user nodes of the provisional user community to determine a final user community; and

in the processing node, processing the final user community to determine when a change in the final user community occurs and then notifying remaining users of the final user community of the change in the final user community.

2. The method of claim 1 wherein processing the adjacency matrix to determine the eigenvectors comprises performing decomposition on the adjacency matrix.

3. The method of claim 1 wherein the adjacency matrix includes quantities of usage activity instances and information associated with a plurality of usage activity types.

4. The method of claim 1, wherein processing the provisional user community to identify and exclude the incorrectly identified user nodes of the provisional user community to determine the final user community comprises processing a spectral clustering of the provisional user community to identify and remove the incorrectly identified user nodes from the provisional user community.

5. The method of claim 1 wherein including the additional user nodes in the provisional user community comprises including the additional user nodes in the provisional user community until conductance of the provisional user community increases.

6. A software apparatus to control a processing node for a communication network having a set of users, the software apparatus comprising:

software that is configured, when executed by the processing node, to direct the processing node to monitor usage activity for the set of users of the communication network, process the usage activity for the set of users to generate an adjacency matrix comprising connectivity information between individual ones of the users of the set, process the adjacency matrix to determine eigenvectors, and if at least two of the eigenvectors are perpendicular, then process the eigenvectors to determine a first user node of the set of users with a highest magnitude along a first eigenvector of the eigenvectors and include the first user node in a provisional user community having shared connectivity, identify additional user nodes of the set of users having high magnitudes along the first eigenvector and that share connectivity with at least one other user node already included in the provisional user community, and include the additional user nodes in the provisional user community until modularity of the provisional user community decreases, process the provisional user community to identify and exclude incorrectly identified user nodes of the provisional user community to determine a final user community, and process the final user community to determine when a change in the final user community occurs and then notify remaining users of the final user community of the change in the final user community; and

a storage system storing the software.

7. The software apparatus of claim 6 wherein the software configured to direct the processing node to process the adjacency matrix to determine the eigenvectors comprises the software configured to direct the processing node to perform decomposition on the adjacency matrix.

8. The software apparatus of claim 6 wherein the adjacency matrix includes quantities of usage activity instances and information associated with a plurality of usage activity types.

9. The software apparatus of claim 6 wherein the software configured to direct the processing node to process the provisional user community to identify and exclude the incorrectly identified user nodes of the provisional user community to determine the final user community comprises the software configured to direct the processing node to process a spectral clustering of the provisional user community to identify and remove the incorrectly identified user nodes from the provisional user community.

10. The software apparatus of claim 6 wherein the software configured to direct the processing node to include the additional user nodes in the provisional user community comprises the software configured to direct the processing node to include the additional user nodes in the provisional user community until conductance of the provisional user community increases.