Method and an apparatus for analyzing a communication network

• US 8,442,073 B2
• Filed: 02/07/2008
• Issued: 05/14/2013
• Est. Priority Date: 10/25/2007
• Status: Expired due to Fees

• Current Assignee: Siemens Healthcare GMBH (Siemens AG)
• Original Assignee: Siemens AG
• Inventors: Skubacz, Michal, Viermetz, Maximilian
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US12/068,561
• Publication Number:
  US 20090109872A1
• Time in Patent Office: 1,923 Days
• Field of Search: 370/254
• US Class Current: 370/474
• CPC Class Codes: H04L 41/14 Network analysis or design

Abstract

The invention provides a novel method and apparatus for analyzing a communication network such as a computer network or a social network comprising nodes communicating with each other by means of messages. A topic discovery unit is provided for performing a topic discovery on the basis of a message content which can be formed by textual content. A segmentation unit performs a segmentation of a global network graph representing the communication network into topic sub-graphs depending on the discovered topics. A property calculation unit calculates intra-topic network properties and inter-topic network properties of the network nodes. An advantage is that a deeper understanding of the analyzed communication network can be achieved such as communications patterns to identify roles of participating nodes. The method and apparatus according to the present invention can be used to optimize the organization of any communication network.

Claims

1. A method for analyzing a communication network comprising nodes communicating with each other via messages, the method comprising:

detecting messages that are exchanged between the nodes of said communication network;

storing said messages in a message list memory;

identifying communication links within the network, each communication link being identified between a source node and a destination node if and only if a message has travelled on the link from the source node to the destination node;

for each message that has been stored in the message list memory, identifying a content of the message;

performing a topic discovery on the basis of the content of all of said messages;

performing a segmentation of a global network graph representing said communication network into topic sub-graphs depending on the discovered topics, each sub-graph including at least two nodes and the communication link connecting the nodes;

calculating intra-topic network properties of the nodes within their respective sub-graphs; and

calculating inter-topic network properties of the nodes with regard to all sub-graphs by calculating an inter-topic centrality of each node proportionally to a number of sub-graphs to which the respective node is a member of.

2. The method according to claim 1, wherein a calculated network property is formed by a centrality of a node.

3. The method according to claim 1, wherein a calculated network property is formed by a prestige of a node.

4. The method according to claim 1, wherein each message comprises at least an indication of the source node transmitting said message, an indication of the destination node receiving said message, and a message content.

5. The method according to claim 4, wherein the message content is formed by a textual content or by multi media data.

6. The method according to claim 4, wherein said indication of a node is formed by a network address of said node or by a name of said node.

7. The method according to claim 1, wherein said messages are transferred between said nodes via communication channels.

8. The method according to claim 7, wherein the communication channels are wireless communication channels or wired communication channels.

9. The method according to claim 8, wherein said messages are transferred between the nodes via communication channels as electro-magnetic signals.

10. The method according to claim 8, wherein said messages are transferred between said nodes as acoustic signals.

11. The method according to claim 10, wherein the acoustic signals are converted by at least one microphone to corresponding electronic signals.

12. The method according to claim 7, wherein said messages are transferred as data packets via a communication channel.

13. The method according to claim 7, wherein the messages are formed by e-mails transferred via a communication channel.

14. The method according to claim 1, wherein the messages exchanged between the nodes of said communication network are stored in a message list.

15. The method according to claim 1, wherein performing said topic discovery comprises:

extracting keywords from the content of the messages to generate key word vectors;

stemming of the extracted keywords and removing of a stop words;

normalizing the generated keyword vectors using Term Frequency—

Inverse Document Frequency (TF/IDF);

pruning the normalized keyword vectors;

performing a singular value decomposition to reduce the dimensionality of a keyword vector space; and

clustering messages having a similar message content in topic clusters.

16. The method according to claim 15, wherein the messages of a topic cluster are combined during segmentation of said global network graph into a corresponding topic sub-graph.

17. The method according to claim 15, wherein the clustering of the messages is performed based on a Density-Based Spatial Clustering of Applications with Noise (DB-scan).

18. The method according to claim 1, wherein said network is formed by a computer network.

19. The method according to claim 1, wherein said network is formed by a social network.

20. An apparatus for analyzing a communication network comprising nodes communicating with each other via messages, comprising:

a detector to detect messages that are exchanged between the nodes of said communication network;

a message list memory to store the messages;

a topic discovery unit to identify a content of each message and to perform a topic discovery on the basis of the content of all messages;

a segmentation unit to identify communication links within the network, each communication link being identified between a source node and a destination node if and only if a message has travelled on the link from the source node to the destination node, and to perform a segmentation of a global network graph representing said communication network into topic sub-graphs depending on the discovered topics, each sub-graph including at least two nodes and the communication link connecting the nodes; and

a property calculation unit for calculating intra-topic network properties of the nodes within their respective sub-graphs and for calculating inter-topic network properties of the nodes with respect to all sub-graphs by calculating an inter-topic centrality of each node proportionally to a number of sub-graphs to which the respective node is a member of.

21. A non-transitory computer readable storage medium storing a program to control a computer to perform a method for analyzing a communication network comprising nodes communicating with each other via messages, the method comprising:

for each message, identifying a content of the message;

performing a topic discovery on the basis of the content of said messages;

identifying communication links within the network, each communication link being identified if and only if a message has travelled between users on the link;

performing a segmentation of a global network graph representing said communication network into topic sub-graphs by segmenting the communication links depending on the discovered topics;

calculating intra-topic network properties within each sub-graph; and

calculating inter-topic network properties between the sub-graphs by calculating an inter-topic centrality of each node proportionally to a number of sub-graphs to which the respective node is a member of.