METHOD FOR DETECTING COMMUNITIES IN MASSIVE SOCIAL NETWORKS BY MEANS OF AN AGGLOMERATIVE APPROACH

• US 20130198191A1
• Filed: 07/08/2010
• Published: 08/01/2013
• Est. Priority Date: 07/08/2010
• Status: Abandoned Application

• Current Assignee: Telefonica SA
• Original Assignee: Arturo Canales Gonzalez, David Millan Ruiz, Rafael Pellon Gomez-Calcerrada, Rocio Martinez Lopez, Ruben Lara Hernandez
• Inventors: Lara Hernndez, Rubn, Pelln Gmez-Calcerrada, Rafael, Canales Gonzlez, Arturo, Milln Ruiz, David, Martnez Lpez, Roco
• Application Number:
  US13/809,107
• Publication Number:
  US 20130198191A1
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Disclosed is a method for detecting communities in massive social networks by means of an agglomerative approach in which core communities are built and gradually clustered in an iterative manner into higher level communities until the algorithm converges (a stop condition is met), whereby it becomes possible to easily trace how the communities are being formed, resulting in an easily explainable model that allows the detection of overlapping communities. The disclosed method starts from data representing social interactions between individuals, building a weighted social graph where the vertices represent individuals and the links represent social relationships between individuals.

Claims

1. Method for detecting communities in massive social networks by means of an agglomerative approach, where said communities are formed by individuals, where a user previously establishes configuration parameters, said parameters being defined in a range:

d≧

1, NM≧

2, j≧

0, 0≦

const≦

1, 0≦

vt≦

1, α

≧

0 τ

>

0, where a clique is defined as a fully connected subgraph, in which each vertex, which represents an individual, is connected by means of links, which represent a social interaction between the connecting individuals, to the other individuals forming the subgraph, comprising the following phases;

1) building a social graph from the information obtained about each social interaction between pairs of individuals belonging to one and the same social network by assigning a weight to each link between pairs of individuals, said weight representing a strength of the link defined as the intensity of the social interaction between each pair of individuals of the social graph calculated based on the amount of social interactions between each said pair of individuals;

2) analyzing and detecting cliques existing in said social graph, said cliques being fully connected communities formed by at least 3 individuals and the links between said individuals being those which have a link strength value above the parameter “

a”

; and

,

3) merging the clicks first and then merging the communities in an iterative manner until meeting a stop condition, said communities and cliques being those which have a cohesion function value above the parameter “

j” and

said communities and cliques having previously been selected for being merged by means of the analysis and detection of phase

     2) of said communities in each iteration.

2. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 1, wherein the phase of building a social graph, where the input is a set “

I”

of data relating to social interactions between users and where each interaction is defined as “

γ

”

belonging to “

I” and

where said “

γ

”

is described as a tuple (v_i,v_j,t,p₁, . . . ,p_n) where “

v_i” and

“

v_j”

are any two individuals interacting with one another, “

t”

is the moment in which said social interaction occurs and “

p₁, . . . , p_n,”

are the properties of the social interaction, comprising the following steps;

comparing the values “

t”

of each social interaction and identifying a “

t_min”

as the moment in which the first social interaction occurs and a “

t_max”

as the moment in which the last social interaction occurs;

dividing the time interval [t_min, t_max] into a finite number “

d”

of time intervals of the same amplitude;

assigning a link strength value, comprised between “

0” and

“

NM”

, to the links between individuals by means of a function S(v_i,v_j), which combines the values of a function “

S_t”

for each time interval “

d”

, defined by;

S(v_i,v_j)=S_t(v_i,v_j,0)·

w₀+ . . . +S_t(v_i,v_j,d)·

w_d

and where

3. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 2, wherein the phase of selecting cliques, given the graph G=(V,E) as input parameter, comprising the following steps:

creating an empty set, referred to as “

L”

;

detecting the maximum cliques contained in “

G”

, said maximum cliques being those cliques the links of which are contained in “

E_s”

, by means of a click detection algorithm and where the vertices of said cliques are individuals belonging to the social network;

storing said cliques in “

L”

.

5. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 11, wherein the phase of including associated members, where “

Ω

_i”

which is the set of communities resulting from the merger performed in the preceding phase and the graph G=(V,E) is used as an input parameter, comprising the following stages;

creating for each community “

C_j”

belonging to “

Ω

_i”

a set “

W_j”

where the members associated with each community are stored, said associated members being those members having weak links with said community and initializing each of these sets as empty sets; and

,

selecting for each individual, “

v”

belonging to “

V”

, who belongs to less than “

N”

communities, “

N”

being a parameter defined by the user, a set “

Ω

”

contained in “

Ω

_i”

of communities including an individual having a link with “

v” and

not including “

v” and

performing the following sub-stages in an iterative manner with each of the communities “

C_j”

;

creating a set of individuals Dif(C_j,Ψ

)=C_j−

Ψ

made up of the individuals of “

C_j”

who do not belong to “

Ψ

”

;

creating a set of individuals Inters(C_j,Ψ

)=C_j□

Ψ

made up of the individuals of “

C_j”

, such that they are in “

Ψ

”

;

calculating an intensity value of each individual “

v”

with each community “

C_j”

by means of the function defined as;

6. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 5, wherein a phase of including dyads is carried out, said dyads being communities of two members, comprising the following stages:

detecting communities of two individuals contained in the graph “

G”

not belonging to communities of more than two individuals; and

,

storing said communities in the list of communities found in the set “

Ω

_i+1”

.

8. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 1, wherein the social interaction between individuals is selected from telephone calls, emails, SMS, MMS, an electronic social interaction other than the aforementioned and a combination thereof.

9. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 2, wherein the interaction properties are selected from the type of interaction, the type of communication channel and the location information.

10. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 11, wherein the stop condition is selected from:

carrying out a fixed number of iterations defined by the user, “

M”

; and

,

the condition “

Ω

_i+1=Ω

_i”

being met.

11. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 1, wherein the phase of merging cliques which is performed in an iterative manner, having previously created the empty set “

Q_i+1”

with i;

0 . . . M and “

M”

being the number of iterations performed and where the set of maximum cliques “

L”

detected in phase

     2) is used as input parameters defining Ω

₀=L in the first iteration of the phase of merging cliques, comprising the following stages;

selecting, for each community “

C_j”

belonging to “

Ω

_i”

, a set “

U_ij”

contained in “

Ω

_i”

of all the communities including an individual of “

C_j”

;

calculating a cohesion value of the result of merging “

C_j”

with each community of “

U_ij”

by means of a function defined as;

12. Method for detecting communities in massive social networks by means of an agglomerative approach according to claim 3, wherein the click detection algorithm, the graph D=(A,B) given as an input parameter, the set A of vertices of the graph being selected from a set of individuals and a set of communities and the set B of links of the graph being selected from a set of links between individuals and a set of links between communities, comprising the following steps:

selecting a subgraph “

D_i”

contained in “

D”

, “

D_i”

being the graph of a vertex “

i”

, and a triangular matrix “

M_i”

associated with “

D_i”

, said matrix “

M_i”

being the matrix of communications between the vertex “

i” and

the vertices with which it has links; and

,

executing the following sub-phases for each vertex of “

M_i”

with those with which the vertex “

i”

has links;

selecting a clique “

Q”

contained in “

D_i” and

a set of vertices, “

P”

contained in “

A”

, the vertices of which are neighbors of the vertices of “

Q”

;

verifying that the union of “

Q”

with each of the vertices of “

P”

is also a clique;

adding the vertices that verify the preceding phase to “

Q”

; and

,

including “

Q”

in “

L”

when there are no longer vertices to be added to “

Q”

.

4. (canceled)

7. (canceled)