An Incremental Parallel Approach for Finding Communities in Evolving Network

摘要

To reveal the internal functionality and the structure of a network more accurately, it is necessary to break down the network into sub-networks, where each member of a sub-network possess the similar characteristics. In recent years, due to many real-world application (industry andresearch) community detection from real-world networks gain more attention. A good number of researcher propose different approaches to overcome the issues of community detection. Although, most of the conventional approach rely on the premises that networks are static in nature and therewon’t be any alternation with time. Moreover, all these approaches are single machine approach and therefore, as the problem size grows the quality of the result deteriorate. To overcome the demerit of processing massive data in a single machine and to achieve results in reasonable amountsof time, the research attention has recently been turning to parallelizing the technique. Some works are available in finding communities in distributed networks. However, most of them are based on static network and can uncover only disjoint communities, which is not feasible for dynamicor online networks. In this work, we propose a new incremental parallel approach ICDE (Incremental Community Finding in Distributed Evolving Network). ICDE can detect both disjoint and overlapping communities simultaneously in dynamic distributed network. We define a new Affinity score based on intra-community strength between nodes and their neighbors. We also derive a new model to perform community merging, based on common high degree nodes present in both the communities. We tested our algorithm on various real world networks for our experimentation. Results showthat, ICDE produce satisfactory output with respect to various assessment indices.