METHOD OF CHARACTERIZING A SOCIAL NETWORK COMMUNICATION USING MOTIFS

• US 20120290649A1
• Filed: 05/10/2011
• Published: 11/15/2012
• Est. Priority Date: 05/10/2011
• Status: Active Grant

• Current Assignee: Telefonica SA
• Original Assignee: Telefonica SA
• Inventors: Ramirez, Nuria Oliver, Zhao, Qiankun
• Granted Patent: US 8,560,681 B2
• Time in Patent Office: Days
• US Class Current: 709/204
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 51/52 for supporting social networking services
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04W 4/21 for social networking applications

Abstract

The present disclosure relates generally to methods for characterizing communication networks, and more particularly to methods of characterizing the propagation of information throughout communications in such networks.

Claims

1. A method for characterizing a network communication, for each communication interaction between two users, u_i^o, u_i^d, of said network, the method comprising:

obtaining a temporal annotation t_i of each communication interaction, and a duration δ

_i of each communication interaction,

characterizing, using a computer system, said network communication, thereby creating a communication graph C;

wherein a first communication interaction and a second communication interaction within the network are considered for characterization of such network and form part of a communication graph C if;

a) said first and second communication interactions have at least one user in common; and

,

b) the time lapsed between the end of the first communication interaction and the beginning of the second communication interaction is within a pre-established time window W;

wherein each communication graph C_i^j is formed by i unique users and j communication interactions that fulfil the conditions a) and b) set before.

2. Method according to claim 1, which further comprises the step of filtering out each communication graph with a frequency constraint.

3. Method according to claim 2, in which a communication graph is considered for characterization if the same type of communication graph appears more than a certain number of times in the interaction network.

4. Method according to claim 3, wherein two communication graphs are considered of the same type or equivalent when they share the same topology structure.

5. Method according to claim 1, wherein for a given a support threshold ⊖

, any equivalence class of the communication graphs S={C_i^j(1), C_i^j(2), C_i^j(3), . . . C_i^j(n)} based on graph equivalence with no less than ⊖

communication graphs is referred to as a communication motif.

6. Method according to claim 5, wherein each communication motif is extracted using a process based on an earliest first search EFS.

7. Method according to claim 5, wherein a communication motif is a maximum-flow motif when it maximizes the flow of information within the network.

8. Method according to claim 1, wherein the size of the time window depends on the type of network.

9. Method according to claim 1, wherein a communication graph has to appear more than a certain number of times in the network in order to be considered.

10. Method according to claim 1, wherein said temporal annotation t_i is a timestamp of the beginning of the communication interaction.

11. Method according to claim 1, wherein said temporal annotation t_iis a timestamp of the end of the communication interaction.