Bilkent University
Department of Computer Engineering
CS 590 SEMINAR
Parallel Overlapping Community Detection
Murat Yusuf Taze
MS Student
Computer Engineering Department
Bilkent University
Community detection (aka Community Discovery) can be seen as a network variant of traditional data clustering. To efficiently detect these structures is very useful for a number of applications, ranging from targeted vaccinations and outbreak prevention, viral marketing, many web data analysis tasks such as finding tribes in online information exchanges, data compressing, clustering and to sampling. In this study, we are trying to implement DEMON [1] algorithm in a parallel fashion. The platform that we use is PCJ [2] which is essentially a library for Java language that helps to perform parallel and distributed computations. The PCJ library implements partitioned global address space model. We first partition the data considering load-balance and the communication costs. We then perform the actual DEMON algorithm in each processor. Finally, we collect the communities and merge them accordingly. Our main contributions can be summarized as follows. We first improved merging step of the DEMON algorithm via an inverted index based approach. It works significantly faster than the original algorithm. We then implemented main skeleton of the parallel program using PCJ library. We proposed a degree oriented smart remote access mechanism. Currently, we are working on an efficient partitioning technique and global merging mechanism to carry our existing research even further.
[1] M. Coscia, G. Rossetti, F. Giannotti, and D. Pedreschi. Demon: a local-first discovery method for overlapping communities. In KDD ’12, 2012.
[2] M. Nowicki, P. Bala Parallel computations in Java with PCJ library In: W. W. Smari and V. Zeljkovic (Eds.) 2012 International Conference on High Performance Computing and Simulation (HPCS) IEEE 2012 pp. 381-387
DATE: 04 April, 2016, Monday @ 16:00
PLACE: EA-409