Benchmarks for Overlapping Community Detection Algorithms

Recent studies on networks obtained from different domains such as social networking sites, internet / web-pages, protein-protein interaction networks etc. , have shown that they share many common properties. One of the common properties of all these real networks is that they follow a community structure where the set of nodes with common interest are grouped together. The nodes within a group interact with each other very frequently and have relatively less interaction with the nodes of the other groups. The other essential property observed about these communities is that they have an overlapping nature, where some nodes can be members of more than one community. Several overlapping community detection algorithms like GCE and CFinder were proposed to detect the overlapping nature of communities of a given network. This requires performance comparison of these algorithms on a set of networks with known community structure or in other words a set of benchmark networks. There are different types of benchmark networks. In this work we studied the existing commonly used benchmark, namely, the LFR benchmark. The actual problem of this LFR benchmark is that it can create a network in which every node belongs to at least one community i. e, membership is at least one. But in real networks such as social or biological or computer networks, some nodes may not belong to any community (i. e. , zero membership) but still have sparse interactions with the other nodes that are either members of any community or nodes like them (these are actually called the homeless nodes or orphan nodes). We have extended the presently existing LFR benchmark with orphan nodes. In our experiments we have observed that in some cases extended LFR benchmark (benchmark with orphan nodes or ELFR) is 5 % better than the normal LFR benchmark.