An Assessment of Community Finding Algorithms for Community-Based Message Routing in DTNs

摘要

Previous work has demonstrated that community-finding algorithms can provide useful information for routing algorithms in delay tolerant networks. In this work we investigate which community finding algorithm most effectively informs this routing task. While early community finding algorithms partitioned networks into flat disjoint communities, more recent methods return community structures that can be overlapping and hierarchical. Given this diversity, it seems reasonable to expect that some methods will be better suited to message routing than others. In this paper, we evaluate a number of community finding strategies and find that Link Clustering, which returns overlapping hierarchical clusters, is very effective. We also find that InfoMap performs well - this is somewhat surprising given that InfoMap returns a flat partition of the network, however this may be because the optimization that drives InfoMap is based on flow.