Highlights of research results on Community Detection presented at the ASONAM 2010 Conference

riclage's picture

From 9 to 11 of August I attended the ASONAM 2010 conference in Odense. The city, located in the Funen Island, is the third largest in Denmark and houses the H. C. Andersen Museum, next to place he was allegedly born. As for the conference, for three days it covered topics in social networks analysis and mining, with particular emphasis to the detection of communities and groups, and issues with security and terrorism networks. I attended mostly the sessions related to the first emphasis and will, thus, concentrate on summarizing them.

Before, it is worth noting that conference had researcher from multiple disciplines, including computer science, mathematics, and social sciences. The focus on multidisciplinary studies was evident from the start. The first keynote speaker, Stanley Wasserman from the Indiana University, warned for the need of a multidisciplinary view of social network analysis. The presenter briefly summarized early pioneer works that are often neglected by researchers of other fields.

Without disagreeing, part of the reason for this lack of consensus on referencing previous works could be the large and increasing of publications on social networks acknowledged by Wasserman. It is an exhaustive task to include all the relevant references, especially because, throughout its recent history, many different terms were used to refer to the same concept. Thus, it seems, the origin of the problem is not necessarily the negligence of authors but the difficulty of addressing similar topics with different terminologies. Nevertheless, a conference like ASONAM, bringing together researchers from different fields, was an important contribution to reducing these inconsistencies.

In the topic of community detection, two papers are worth mentioning. The first, “Incremental Detection of Local Community Structure” by Karl Branting proposes two new algorithms for detecting community structure in static graphs. The algorithms performed better than traditional approaches in graphs with power law degree distributions or in random distributions, but not in certain ranges between the two kinds of degree distributions. The second paper, “Tracking the Evolution of Communities in Dynamic Social Networks” by Greene at al. , proposes a new approach to detect the evolution of groups of users in social networks. Unlike Branting’s algorithms, the authors’ approach was able to detect communities over discrete time steps with at least the same performance of algorithms over static networks in synthetic graphs. The paper is very well written and technically sound, and in fact won the second best paper award at the conference.

The paper “Community Aware Personalized Web Search” by Shafiq et al. uses the concept of community to refer to a user’s close friends in a social network and their activity. Data from a user community is used to weight search engine results with personalized results. This is done in three ways. One, it uses information from the user profile such as personal information, blogging activity, and links shared. Two, it uses similar information from the user’s friends to try to match similar interests. Three, it weights the recommendation based on trust measure calculated from the distance between the user and friends, friends of friends, and so on. The paper, however, lacks empirical evidence of its improvement over traditional search algorithms.

Finally, the paper “Optimizing Multiple Centrality Computations for Reputation Systems” by Weth et al. proposes two optimization techniques to the computation of centrality measures in a graph. This is done in the context of a feedback graph, often used for trust measures. The authors cover in their evaluation PageRank, HITS and Positional Weakness (PW) algorithms for the optimization techniques. The first technique is the Loop Fusion which combines together iterations that perform the same tasks over different datasets. The second is the Re-Use of Computation Results. That is, after the computation of one centrality measure, some of its results are used in the computation of the next. While the reuse performed well only in particular cases, the Loop Fusion performed consistently better than other approaches evaluated by the authors.

Other papers presented at the conference were worth attending the sessions and the conference overall. The conference was a good experience also for meeting the authors and other participants present.