In this paper we propose two novel methods for analysing data collected from online social networks. In particular we will do analyses on Vkontake data (Russian online social network). Using biclustering we extract groups of users with similar interests and nd communities of users which belong to similar groups. With triclustering we reveal users' interests as tags and use them to describe Vkontakte groups. After this social tagging process we can recommend to a particular user relevant groups to join or new friends from interesting groups which have a similar taste. We present some preliminary results and explain how we are going to apply these methods on massive data repositories.
Recently the focus of social network analysis shifted from 1-mode networks, like
friend-to-friend, to 2-mode [
This interest is not only pure academic but caused by modern business requirements. Thus, every user of a social networking website has not only friends, but he also has speci c pro le features, e.g. he can belong to some groups of users, indicate his tastes or books he read etc. These pro le attributes are able to describe the user's tastes, preferences, attitudes, which is highly relevant for business oriented social networking web sites owners. Finding bicommunities and tricommunities can help the networking site owners to analyze large groups of their users and adjust their services according to users' needs which may in the end result in nancial or other bene ts.
There is a large amount of network data that can be represented as bipartite or tripartite graphs. Standard techniques like \maximal bicliques search" return a huge number of patterns (in the worst case exponential w.r.t. the input size). Therefore we need some relaxation of the biclique notion and good interestingness measures for mining biclique communities.
Applied lattice theory provides us with a notion of formal concept [
A concept-based bicluster [
For analyzing three-mode network data like folksonomies [
The remainder of the paper is organized as follows. In section 2 we describe some key notions from Formal Concept Analysis. In section 3 we introduce a model for our new pseudo-triclustering approach. In section 4 we describe a dataset which is a sample of users, their groups and interests from the Vkontakte (http://vk.com) social networking web site. We present the results obtained during experiments on this dataset in Section 5. Section 6 concludes our paper and describes some interesting directions for future research. 2
The formal context in FCA [
A0 = fm 2 M j gIm for all g 2 Ag; B0 = fg 2 G j gIm for all m 2 Bg: (1)
The operator 00 (applying the operator 0 twice) is a closure operator : it is
idempotent (A0000 = A00), monotonous (A B implies A00 B00) and extensive
(A A00). The set of objects A G such that A00 = A is called closed. The same
is for closed attributes sets, subsets of a set M . A couple (A; B) such that A G,
B M , A0 = B and B0 = A, is called formal concept of a context K. The sets
A and B are closed and called extent and intent of a formal concept (A; B)
correspondingly. For the set of objects A the set of their common attributes A0
describes the similarity of objects of the set A, and the closed set A00 is a cluster
of similar objects (with the set of common attributes A'). The relation \to be
a more general concept" is de ned as follows: (A; B) (C; D) i A C. The
concepts of a formal context K = (G; M; I) ordered by extensions inclusion form
a lattice, which is called concept lattice. For its visualization the line diagrams
(Hasse diagrams) can be used, i.e. cover graph of the relation \to be a more
general concept". In the worst case (Boolean lattice) the number of concepts
is equal to 2fmin jGj;jMjg, thus, for large contexts, FCA can be used only if the
data is sparse. Moreover, one can use di erent ways of reducing the number
of formal concepts (choosing concepts by their stability index or extent size).
The alternative approach is a relaxation of the de nition of formal concept as a
maximal rectangle in an object-attribute matrix which elements belong to the
incidence relation. One of such relaxations is the notion of an object-attribute
bicluster [
m g' m'' m' g
g''
1. For any bicluster (A; B) 2G 2M it is true that 0 2. OA-bicluster (m0; g0) is a formal concept i = 1. 3. If (m0; g0) is a bicluster, then (g00; g0) (m0; m00). (A; B) 1.
Let (A; B) 2G 2M be a bicluster and min be a non-negative real number such that 0 min 1, then (A; B) is called dense, if it ts the constraint (A; B) min. The above mentioned properties show that OA-biclusters di er from formal concepts by the fact that they do not necessarily have unit density. Graphically it means that not all the cells of a bicluster must be lled by a cross (see g. 1).
Let KUI = (U; I; X U I) be a formal context which describes what interest i 2 I a particular user u 2 U has. Similarly, let KUG = (U; G; Y U G) be a formal context which indicates what group g 2 G user u 2 U belongs to.
We can nd dense biclusters as (users; interesets) pairs in KUI using the
OAbiclustering algorithm which is described in [
By means of triclustering we can also reveal users' interests as tags which describe similar Vkontakte groups. So, by doing this we can solve the task of social tagging and recommend to a particular user relevant groups to join or interests to indicate on the page or new friends from interesting groups with similar tastes to follow.
To this end we need to mine a (formal) tricontext KUIG = (U; I; G; Z U I G), where (u; i; g) is in Z i (u; i) 2 X and (u; g) 2 Y . A particular tricluster has a form Tk = (iX \ gY ; uX ; uY ) for every (u; g; i) 2 Z with jjiiXX [\ggYY jj , where is a prede ned threshold between 0 and 1. We can calculate the density of Tk directly, but it takes O(jU jjIjjGj) time in the worst case, so we prefer to de ne the quality of such tricluster by density of biclusters (gY ; uY ) and (iX ; uX ). We propose to calculate this estimator as b(Tk) = (gY ;uY ) +2 (iX ;uX ) ; it's obvious that 0 b 1. We have to note that the third component of a (pseudo)tricluster or triadic formal concept usually is called modus.
The algorithm scheme is displayed in Fig. 2 4
For our experiments we collected a dataset from the Russian social networking site Vkontakte. Each entry consisted of the following elds: id, userid, gender, family status, birthdate, country, city, institute, interests, groups. This set was divided into 4 subsets based on the values of the institute eld, namely students of two major technical universities and two universities focusing on humanities and sociology were considered: The Bauman Moscow State Technical University, Moscow Institute of Physics and Technology (MIPT), the Russian State University for Humanities (RSUH) and the Russian State Social University (RSSU). Then 2 formal contexts, users-interests and users-groups were created for each of these new subsets. 5
We performed our experiments under the following setting: Intel Core i7-2600 system with 3.4 GHz and 8 GB RAM. For each of the created datasets the following experiment was conducted: rst of all, two sets of biclusters using various minimal density constraints were generated, one for each formal context. Then the sets ful lling the minimal density constraint of 0.5 were chosen, each pair of their biclusters was enumerated and the pairs with su cient extents intersection ( ) were added to the corresponding pseudo-tricluster sets. This process was repeated for various values of .
As it can be seen from the graphs and the tables, the majority of pseudotriclusters had value of 0.3 (or, to be more precise, 0.33). In this series of experiments we didn't reveal manually any interests which are particular for certain universities, but the number of biclusters and pseudo-triclusters was relatively higher for Bauman State University. This is a direct consequence of the higher users' number and the diversity of their groups.
Some examples of obtained biclusters and triclusters with high values of density and similarity are presented below.
Example 1. Biclusters in the form (U sers; Intersts) .
= 83; 33%, generator pair: f3609; homeg, bicluster: (f3609; 4566g; ff amily; work; homeg)
= 83; 33%, generator pair: f30568; orthodox churchg, bicluster: (f25092; 30568g; fmusic; monastery; orthodox churchg) = 100%, generator pair: f4220; beautyg, bicluster: (f1269; 4220; 5337; 20787g; flove; beautyg)
E.g., the second bicuster can be read as users 25092 and 30568 have almost all \music", \monastery", \orthodox church" as common interests. The pair generator shows which pair (user; interest) was used to build a particular bicluster. Example 2. Pseudo-triclusters in the form (U sers; Intersts; Groups).
Bicluster similarity = 100%, average density b = 54; 92%.
Users: f16313; 24835g, Interests: fsleeping; painting; walking; tattoo; hamster; impressionsg, Groups: f365; 457; 624; : : : ; 17357688; 17365092g
This tricluster can be interpreted as a set of two users who have on average 55% of common interests and groups. The two corresponding biclusters have the same extents, i.e. people with almost all interests from the intent of this tricluster and people with almost all groups from the tricluster modus coincide. 6
The approach needs some improvements and ne tuning in order to increase
the scalability and quality of the community nding process. We consider
several directions for improvements: Strategies for approximate density
calculation; Choosing good thresholds for n-clusters density and communities
similarity; More sophisticated quality measures like recall and precision in Information
Retrieval; The proposed technique also needs comparison with other approaches
like iceberg lattices ([
Finally, we conclude that it is possible to use our pseudo-triclustering method for tagging groups by interests in social networking sites and nding tricommunities. E.g., if we have found a dense pseudo-trciluster (U sers, Groups, Interests) we can mark Groups by user interests from Interests. It also makes sense to use biclusters and triclusters for making recommendations. Missing pairs and triples seem to be good candidates to recommend the target user other potentially interesting users, groups and interests.
Acknowledgments. We would like to thank our colleagues Vincent Duquenne, Sergei Kuznetsov, Sergei Obiedkov, Camille Roth and Leonid Zhukov for their inspirational discussions, which directly or implicitly in uenced this study.