DyPerm: Maximizing Permanence for Dynamic Community Detection

Autor:	Agarwal, Prerna, Verma, Richa, Agarwal, Ayush, Chakraborty, Tanmoy
Rok vydání:	2018
Předmět:	Computer Science - Social and Information Networks Physics - Physics and Society
Druh dokumentu:	Working Paper
Popis:	In this paper, we propose DyPerm, the first dynamic community detection method which optimizes a novel community scoring metric, called permanence. DyPerm incrementally modifies the community structure by updating those communities where the editing of nodes and edges has been performed, keeping the rest of the network unchanged. We present strong theoretical guarantees to show how/why mere updates on the existing community structure leads to permanence maximization in dynamic networks, which in turn decreases the computational complexity drastically. Experiments on both synthetic and six real-world networks with given ground-truth community structure show that DyPerm achieves (on average) 35% gain in accuracy (based on NMI) compared to the best method among four baseline methods. DyPerm also turns out to be 15 times faster than its static counterpart. Comment: 4 tables, 3 figures, Accepted in n 22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2018
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1802.04593 Zobrazit plný text záznamu View this record from Arxiv