Superspreaders and superblockers based community evolution tracking in dynamic social networks

摘要

Detecting and tracking communities in dynamic social networks has been a grand multidisciplinary challenge. There are two key steps in tracking the community evolution of dynamic social networks, including dynamic community detection and evolutionary events identification. For dynamic community detection, incremental clustering has been used as one of the most efficient methods; however, incrementally detecting network communities may result in partition errors such that continuous error accumulation will cause a discrepancy between the computed community structure and the underlying ground-truth. For evolutionary events identification, core-node-based methods have been widely employed; however, they do not distinguish between the heterogeneous contributions of core nodes to different evolutionary events, thereby resulting in a reduced accuracy of evolutionary event identification. This paper introduces a novel two-stage method that circumvents both of these problems simultaneously. Firstly, we propose an error accumulation sensitive (EAS) incremental community detection method for dynamic social networks. In our novel EAS method, rather than updating the community structure partially, a dynamic network snapshot is totally re-partitioned once the error accumulation degree of incremental clustering exceeds a pre-defined threshold. Secondly, to identify different critical evolution events, we introduce a superspreaders and superblockers (SAS) based community evolution tracking method for dynamic social networks which utilizes the properties of superspreader and superblocker nodes, the two types of core nodes related to spreading outbreaks in social networks. Experiments conducted on artificial and real-world social networks demonstrate that our proposed method can both efficiently detect dynamic network communities and accurately identify all critical evolutionary events, outperforming a total of eight competing methods. Our two-stage EAS-SAS approach could thus represent a potential method of choice for many real-world applications to community discovery and community evolution tracking in dynamic social networks.