METHOD FOR DETECTING COMMUNITIES IN MASSIVE SOCIAL NETWORKS BY MEANS OF AN AGGLOMERATIVE APPROACH
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
12 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. - View Dependent Claims (2, 3, 5, 6, 8, 9, 10, 11, 12)
- d≧
-
4. (canceled)
-
7. (canceled)
Specification