| dc.description.abstract | Methods for detecting community structures in graphs already exist for many years. This subject is studied by physicists, sociologists and also computer scientists. Traditional methods consider only the vertices and edges, we call this graph data. In social networks much more information, in addition to the graph data is available. This can be demographical information, hobbies or any other interest people put online; we refer to this kind of data as description data. Traditional methods try to partition the vertices in groups according to a quality measure like modularity. These methods do not allow overlap; all vertices are member of exactly one group.
In real social networks, communities have overlap, for example your friends and your family. Thus, a good method for finding communities in social networks should allow communities to overlap. Other interesting information can be obtained by exploiting the description data. A very useful application is identifying which elements of the description data characterize a community.
In this thesis we study this problem, with the goal of finding the top-$k$ communities in a certain data set. We introduce an algorithm which alternates between two steps. The first is finding closely linked vertices on the graph side with a fast and effective hill climbing algorithm. The other is reducing the description complexity of this community. The algorithm starts with a candidate set, and the algorithm is applied on each community one by one. This allows communities to overlap with the communities found before.
To evaluate our methodology, we performed experiments on real world data obtained from a number of online social networks, i.e. LastFM, Delicious, and Flickr. The results show that the proposed method identifies interesting and overlapping communities, characterized by detailed descriptions. Visualizations of both the subgraphs and the descriptions contribute to an easier interpretation and thus better understanding of the communities.
At the end we are able to find cohesive communities with concise descriptions, in large data sets, within a relatively short amount of time. | |
