DEIM Forum 2016 D2-5

Comparison of Community Detection Methods for Facebook Ego Network
Yixuan He†

Kazuya Uesato†

Hayato Yamana†‡†Graduate School of Fundamental Science and Engineering, Waseda University, 3-4-1 Okubo, Shinjuku-ku Tokyo,Japan‡Faculty of Science and Engineering, Waseda University, 3-4-1 Okubo, Shinjuku-ku Tokyo, Japan‡National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, Japan
E-mail: {pandaxuan, k.uesato, yamana}@yama.info.waseda.ac.jp

Abstract: People tend to build and maintain their friendship relying on SNS nowadays. Thus, the problem of how toorganize the social network accurately and automatically has become important to be considered. As this problem draws a lotof attention from both users and companies, there already existed many SNS providing such functions, such as Twitter list,
Facebook lists, etc. However, the functions are laborious, means it requires users to manually organize and update their friends’
circles or lists every time they add new friends. Instead of using the functions, we may adopt community clustering methodsfor SNS. In this research, we applied three different common clustering methods to SNAP Facebook dataset and compared theaccuracy of these three methods to confirm the adoptability for organizing social network accurately and automatically. Ourresult shows that LDA performs the best because both of its complexity compared to k-means and of free from setting thenumber of communities compared to HDP.
Keyword:

Facebook, Data Clustering, Data Mining
common attributes. Neither works particularly satisfactory.

1. INTRODUCTION
Recently, with the development of computer andFirstly, it is laborious for users since every time they add

capable devices, it is hard to imagine life without thesome new friends or every time they grow some newInternet. Also, with the development of the Internet, thecommon attributes with their old friends, a manually

new communication media and technologies, SNS, which

updating of the groups is required. The second works evenrefers to Social Networking Services, have drawn morepoorly especially when the profile information is missing

and more attention from users and researches.

or withheld.

As one of the most popular and successful Social

In this paper, in order to confirm the adoptability

ancurrent clustering methods for organizing social networkindispensable role in providing a great platform for people

accurately and automatically, we compare the accuracy ofand friends not only to share their own feelings, but also

different clustering methods, k-means, Latent Dirichlet

to make new friends, maintain old ties, and deeper current

Allocation (LDA) and Hierarchical Dirichlet Process

relationships. By using Facebook, people can also update(HDP), using Facebook Data from SNAP, which refers totheir friends’ current life, for instance, how other students

Stanford Network Analysis Platform. Then, we evaluate

in the same university think about some classes, how otherthe results by using the ground truth provided by SNAP 1NetworkServices,

Facebook,undeniably

plays

people in the same fashion club think about the latest

We choose k-means because we can apply this method

trend. Same as real life, usually people can also define andwith different values of k. Similarly, LDA also requires anorganize their friends into different friend circles.

assignment of the number of circles, k. However, different

Therefore, it is common for users to expect that feeds

from k-means, LDA assigns a document to a mixture ofposted by the people in the same group could be organized

topics. Each document is categorized by one or more

to show up at the same time. Currently, most of the famous

topics, for instance, 50% Topic A, 30% Topic B, 20%

Social Network Service, such as circles on Google+, lists

Topic C, etc. Hence, in most case, LDA gives a betteron Facebook and Twitter, etc. provide such functions.

result than k-means because of its complexity compared toHowever, generally they all either require users tok-means. So, in this paper, we want to confirm which

manually categorize their friends into those groups or use

method is the best in the three method for determininga naïve fashion by clustering friends who share somefriends’ circles using SNAP Facebook dataset. While thenumber of groups must be pre-specified for the twoLars et al. [3] proposed a method to recognize one

methods above all, the number of k could be automaticallyuser’sromantic

partnerusing

Facebookdatabyinferred from the data when using HDP. In our research,developing a new measure of tie strength – “dispersion”,

we also use HDP to see how different it is when using

which implies two people’s mutual friends are not

LDA and its advanced version, HDP.

well-connected.

In the reminder of the paper, in Section 2, we present

In [4], Adrija identified potential social ambassadors of

the related work in ego network field. And in Section 3

Facebook brand pages of mobile service providers andand 4, we describe the methodology employed and theevaluated the results to be valid by matching with thesubsequent experimental results, respectively. Section 5

opinions provided by domain experts. In their future work,

aims to give the evaluation results of our experiments.

they also mentioned the hindrance of data collecting

Finally, we conclude our paper and discuss about thebecause of the Facebook privacy setting.

limitation and future work of this paper in the last section.

2.2. Research related to Ego Network
In R.I.M et al. work [5], they utilized data on

2. RELATED WORKS

frequencies of bi-directional posts to define edges andThere is a large amount of relevant research based on

create ego network using two Facebook datasets and one

Facebook and ego network. However, most of theTwitter dataset. They clustered the dataset into 4 clusters

researches focus on either improving the accuracy ofeach of which is called “layer.” The frequency of contact

community detection by combining existed methods orwithin each layer varies depending on layers. For example,

creating new models, little of them tried to compare thein the Facebook data case, the contact frequencies are 1.5,

effect of different clustering methods.

4.3, 10.7 and 27.0 for each cluster. They analyzed the data

Furthermore, due to the difficulty for non-Facebook

using two different clustering techniques: k-means andresearch to obtain the Facebook data, many research based

DBSCAN, a density-based clustering technique. Theyon Facebook are written by people who work in Facebook.

obtained similar results and declared that k-means works

SNAP Facebook Dataset is a dataset provided by Stanford

good enough if considering the simplicity of k-means.

and has not drawn much attention from researchers andThe work of Jaewon et al. [6] chose 13 differentthus has been used in a small number of research papers.

commonlyTo the best of our knowledge, our paper is the first paper

communities

comparing k-means, LDA and HDP using SNAP Facebook

sensitivity, respectively by using a set of 230 large

dataset.

real-world social networks in SNAP. Although their

2.1. Research related to Facebook

research did a comparison by methods using SNAP data,

Sungkyu et al.[1] presented how activities on Facebook
are associated with the depressive states of users. Theirusedstructuralanddefinitions

examinedtheirofnetwork

robustness

andthey did not use any small-sized, anonymized data such as
SNAP Facebook dataset.

application

In another work written by Jaewon and Jure et al. [7],implemented within Facebook and conducting face-to-facethey presented a method called BIGCLAM, which is aninterviews. Their study was novel in some perspectives:

example of a bipartite affiliation network model. Theyboth online Facebook data and offline interview data

successfully dealt with the detection of overlapping,

within some time period are used, these data allow them tohierarchicallycompare the relevance between the changes of users’communities with relatively higher accuracy.

methodology

wasbasedonaWeb

depression rate and the changes of Facebook usage. Therenested,

aswellas

non-overlapping

Julian et al. [8] extracted communities from both theare also several limitations in their research: most of theedge

respondents are found to be more educated and areimproved the accuracy of community detection withdisproportionately in male for instance.

relatively high speed. Moreover, besides detecting theIn Zubeida’s work et al. [2], they presented an analysisof graph search on Facebook in order to highlight howstructureandnode

attributes(CESNA).

Theycommunities, it can also help to find the interpretation ofthe detected communities.

easy it is to access large amount of personal information
though Facebook’s graph search. Besides, they determined

3. METHODOLOGY

whether the increase of Facebook friends’ number has an

3.1. Dataset

impact on the increase of the searching results

In this research, SNAP Facebook Dataset is used. Thisdataset consists of information of friends’ circles fromFacebook,forinstance,

theprofilesforeach

3.2. Applying k-means, LDA and HDP

user

Both K-means and Latent Dirichlet Allocation (LDA)(features), circles and network. Data is collected fromare unsupervised learning algorithms. It means before

participants who voluntarily provided their Facebook

clustering, the user should decide a priori value for theinformation to a Facebook app. To protect personalparameter K. In our research, in order to simplify the

information, all the data has been anonymized and theprocess of evaluation, we set the value of K equals to theinterpretation has all been obscured. The details of thisvalue of the ground truth. For example, for ego node 0, ifdataset is shown as below:

the ground truth of friends’ circles is 24, we assign the KTab. 1 Data Statistics of Facebook

1equals to 24. Unlike the k-means and LDA, HDP does not
require a priori decision of K. Instead, it can automaticallyassign an appropriate value of K according to the data thatis given. In our research, we used sklearn 2 , which is amachine-learning library for Python, to calculate theclustering results of k-means. For both LDA and HDP, weuse gensim 3 , which is a topic-modeling library for Python.

4. RESULTS AND EVALUATION 1
In this section, we will show the results of clustering. In
4.1, we introduce the evaluation method that we use in ourresearch. In 4.2, we will present the evaluation results.
In this Dataset statistics, “nodes” represents the numberof friends; “Edges” represents the number of edges in thenetwork; “Nodes in largest WCC” and “Edges in largest
WCC” represents the number in the largest weakly
connected component of nodes and the number of edges
respectively; “Average clustering coefficient” means ameasure of the degree to which nodes in a graph tend tocluster together. “Number of triangles” represents thenumber of triples of connected nodes (considering thenetwork as undirected), “Fraction of closed triangles”

4.1. Evaluation Method
In this paper, we adopt Purity[9], which is a simple
and transparent evaluation measure, as our evaluation
method. The calculation of Purity follows two steps.
Firstly, we label each cluster as the class in which themost frequent class is included. Second, the accuracy iscomputed by counting the number of correctly assigned
data followed by dividing it by N, which is the total
number of the points. For example, we assume that wehave clusters as showing below:

represents the number of connected triples of nodes.
“Diameter(longestmaximum

undirectedshortestpath)”shortest

pathrepresents

thelengthand“90-percentile effective diameter” represents the 90-th
percentile of undirected shortest path length distribution. 1
They also obtained the ground-truth by hand labeling by
volunteer participants.
Thus, we can see that in our dataset, there are 4,039
nodes and 88,234 edges in total. Since this Facebookgraph is undirected and consists of friends of one ego node,
which makes it possible to reach any nodes from any
nodes in the graph, the number of nodes and edges inlargest Weakly Connected Component and in Strong
Connected Component keep the same to the original value.
Besides, due to the small number of participants, theaverage clustering coefficient is also small. In ourresearch, we use their ground-truth as our ground-truth.

Fig. 1 Example of Purify [9]It is obvious that, crosses occur the most in cluster 1,circles occur the most in cluster 2 and diamonds occur themost in cluster 3. So, when we evaluate the accuracy ofthe clustering results, we set cluster 1 as “Cluster Cross”,
cluster 2 as “Cluster Circle” and cluster 3 as “Cluster
1“Stanford Network Analysis Project”, Jure Leskovec,
http://snap.stanford.edu/index.html, access at Jan 6, 2015
2
scikit-learn, http://scikit-learn.org/stable/, access at
Jan 6, 2015
3
gensim, https://radimrehurek.com/gensim/, access at
Jan 6, 2015

Diamond”. The total number of dots is 17, so the Purity

into consideration. Firstly, in our research, we only

can be calculated as (1/17) ×(5+4+3) ≈ 0.71 [9]consider the features of users’ profiles information while

The formula can be represented as:purity(Ω , Ç) =!
!

*edge information, which refers to the connections between! 𝑚𝑎𝑥! |𝜔! ∧ 𝑐! |friends, is also possibility to be utilized. Secondly, in the(1)features files, the rate of the appearance of 1s and 0s is

where Ω = {ω 1 , ω 2 , ω 3 , ω 4 …, ω K } is the set of clusters
and C = {c 1 , c 2 , c 3 , …, c J } is the set of classes.

very low. It means, most of the features are 0s. The
problem of the rarely occurrence of 1s need to beconcerned. Although we chose these three clustering
methods because of its popularity of using, it is possible

4.2. Results and Evaluation
The clustering result of our evaluation is shown inthese three methods are not suitable for this kind ofTable 2. For k-means and LDA, since the k is pre-set to besmall-size, anonymized dataset. Last, in our research, wethe same as the ground truth, we can compute the accuracy

did not consider overlapping, hierarchically communities.

directly.

However,

communities

isforHDP,

automaticallysincetheassigned,

numberinorderofto

calculate the Purity, we combined small groups together tohave a set of large clusters. We did the experiments fourtimes. The results keep changing each time we run theprogram, which is because for k-means, it uses a randomly
chosen starting configuration thus different starting point
gives different clustering results, and for LDA and HDP,
these two methods use randomness when training and ininference steps thus also returns different results. From
the results, we can find that LDA outperforms the othertwo methods in general. But it does not show a big
difference

among

these

threemethods.

Thus,

if

considering the simplicity of k-means, we confirm thatk-means is good enough for community detection whenusing small size dataset.
Experimenttrial
1 st time
2 nd time
3 rd time
4 th time

Tab. 2 Evaluation results
Accuracy
Accuracy(k-means)(LDA)
0.25890.23210.2411
0.25450.28570.25000.27230.2813

Accuracy(HDP)
0.26790.2232
0.23660.2277

5. CONCLUSION
In this paper, we compared three different commonlyused clustering methods using SNAP Facebook dataset. Ingeneral, LDA performs the best because of its complexity
compared to k-means and the possibility of assigning thenumber of communities compared to HDP. However, we
can also find that there is not a big difference among theresults by using these three methods. Thus, due to thesimplicity and convenience, we confirm that k-means
works well when categorizing, detecting the communities.
There is still some future work that could be done.
From the results, we can see that the accuracy is not goodenough. There are many perspectives that need to be taken

REFERENCE[1] Sungkyu Park1 Inyeop Kim2⇤ Sang Won Lee3Jaehyun Yoo3 Bumseok Jeong3 Meeyoung Cha,
Manifestation of Depression and Loneliness on
Social Networks: A Case Study of Young Adults on
Facebook, Proc. of CSCW ’15, Vancouver, BC,Canada, 2015[2] Zubeida Casmod Khan, Thulani Mashiane, An
Analysis of Facebook’s Graph Search, Proc. ofInformation Security for South Africa (ISSA), 2014
[3] Lars
Backstrom,
JonKleinberg,
Romantic
Partnerships and the Dispersion of Social Ties: ANetwork Analysis of Relationship Status onFacebook, Proc. of CSCW’14, Baltimore, Maryland,USA, 2014
[4] Adrija Majumdar, Debashis Saha, Parthasarathi
Dasgupta, An analytical method to identify social
ambassadors for a mobile service provider’s brandpage on Facebook, Proc. of 2015 Applications andInnovations in Mobile Computing (AIMoC), 2015
[5] R.I.M. Dunbara, Valerio Arnaboldia,b, Marco Contib,
Andrea Passarellab, The structure of online socialnetworks mirrors those in the offline world, SocialNetworks, Vol.43, pp.39–47, 2015[6] Jaewon Yang, Jure Leskovec, Defining andEvaluating
NetworkCommunities
basedonGround-truth, Proc. of 2012 IEEE International
Conference on Data Mining (ICDM), 2012[7] JaewonYang,
JureLeskovec,
Overlapping
Community Detection at Scale: A Nonnegative
Matrix Factorization Approach, Proc. of WSDM’13,
February 4–8, 2013, Rome, Italy, 2013[8] Jaewon Yang, Julian McAuley, Jure Leskovec,
Community Detection in Networks with Node
Attributes, Proc. of 2013 IEEE 13 th International
Conference on Data Mining, 2013[9] Introduction to Information Retrieval, Christopher D.
Manning, Prabhakar Raghavan and Hinrich Schütze,Introduction to Information Retrieval, Cambridge
University Press, 2008