Nam P. Nguyen
ABSTRACT
Many practical problems on Mobile networking, such as routing strategies in MANETs, sensor reprogramming in WSNs and worm containment in online social networks (OSNs) share an ubiquitous, yet interesting feature in their organizations: community structure. Knowledge of this structure provides us not only crucial information about the network principles, but also key insights into designing more effective algorithms for practical problems enabled by Mobile networking. However, understanding this interesting feature is extremely challenging on dynamic networks where changes to their topologies are frequently introduced, and especially when network communities in reality usually overlap with each other. We focus on the following questions (1) Can we effectively detect the overlapping community structure in a dynamic network? (2) Can we quickly and adaptively update the network structure only based on its history without recomputing from scratch? (3) How does the detection of network communities help mobile applications? We propose AFOCS, a two-phase framework for not only detecting quickly but also tracing effectively the evolution of overlapped network communities in dynamic mobile networks. With the great advantages of the overlapping community structure, AFOCS significantly helps in reducing up to 7 times the infection rates in worm containment on OSNs, and up to 11 times overhead while maintaining good delivery time and ratio in forwarding strategies in MANETs.
Supplemental Material
- T. N. Dinh, Y. Xuan, and M. T. Thai. Towards social-aware routing in dynamic communication networks. IPCCC, '09.Google Scholar
- B. Pasztor, L. Mottola, C. Mascolo, G. Picco, S. Ellwood, and D. Macdonald. Selective reprogramming of mobile sensor networks through social community detection. Wireless Sensor Networks, '10. Google ScholarDigital Library
- Z. Zou, G. Cao, S. Zhu, S. Ranjan, and A. Nucci. A social network based patching scheme for worm containment in cellular networks. In INFOCOM, '09.Google Scholar
- N. P. Nguyen, T. N. Dinh, Y. Xuan, and M. T. Thai. Adaptive algorithms for detecting community structure in dynamic social networks. INFOCOM, '11.Google Scholar
- M. Girvan and M. E. J. Newman. Community structure in social and biological networks. PNAS, '02.Google Scholar
- M. A. Porter, J-P. Onnela, and P. J. Mucha. Communities in networks. Notices of the AMS, '09.Google Scholar
- N. P. Nguyen, Y. Xuan, and M. T. Thai. A novel method for worm containment on dynamic social netowrks. MILCOM, '10.Google Scholar
- G. Palla, I. Derenyi, I. Farkas1, and T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, '05.Google Scholar
- A. Lancichinetti, S. Fortunato, and K. Janos. Detecting the overlapping and hierarchical community structure in complex networks. New J. of Phys., '09.Google Scholar
- Steve Gregory. Finding overlapping communities in networks by label propagation. New J. of Physics, '10.Google Scholar
- Y-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng. Anlyzing communities and their evolutions in dynamic social networks. ACM TKDD, '09. Google ScholarDigital Library
- R. Cazabet, F. Amblard, and C. Hanachi. Detection of overlapping communities in dynamical social networks. In SocialCom, '10. Google ScholarDigital Library
- L. Peel. Estimating network parameters for selecting community detection algorithms. FUSION, '10.Google Scholar
- A. Lancichinetti and S. Fortunato. Community detection algorithms: A comparative analysis. Phys. rev. E. 80, '09.Google Scholar
- D. Duan, Y. Li, Y. Jin, and Z. Lu. Community mining on dynamic weighted directed graphs. In CNIKM, '09. Google ScholarDigital Library
- M-S. Kim and J. Han. A particle-and-density based evolutionary clustering method for dynamic networks. VLDB Endow., 2009. Google ScholarDigital Library
- S. Fortunato and C. Castellano. Community structure in graphs. arXiv, '07.Google Scholar
- A. Lazar, D. Abel, and T. Vicsek. Modularity measure of networks with overlapping communities. Euro. Let., '10.Google Scholar
- F. Radicchi, C. Castellano, F .Cecconi, V. Loreto, and D. Parisi. Defining and identifying communities in networks. Proc. Natl. Acad. Sci. USA, '04.Google Scholar
- J. P. Bagrow Y-Y Ahn and S. Lehmann. Link communities reveal multiscale complexity in networks. Nature, '10.Google Scholar
- S. Fortunato. Community detection in graphs. Phys. Reports, '10.Google Scholar
- J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Statistical properties of community structure in large social and information networks. In WWW08, '08. Google ScholarDigital Library
- C. Lee, F. Reid, A. McDaid, and N. Hurley. Detecting highly overlapping community structure by greedy clique expansion. In KDD, '10.Google Scholar
- P. Hui, E. Yoneki, S. Y. Chan, and J. Crowcroft. Distributed community detection in delay tolerant networks. In MobiArch, '07. Google ScholarDigital Library
- E. M. Daly and M. Haahr. Social network analysis for routing in disconnected delay-tolerant manets. In MobiHoc '07. Google ScholarDigital Library
- P. Hui, J. Crowcroft, and E. Yoneki. Bubble rap: social-based forwarding in delay tolerant networks. In MobiHoc '08. Google ScholarDigital Library
- P. Hui and J. Crowcroft. How small labels create big improvements. PERCOMW, '07. Google ScholarDigital Library
- E. Nathan and A. Pentland. Reality mining: sensing complex social systems. Personal Ubiquitous Comput., '06.Google Scholar
- B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi. On the evolution of user interaction in facebook. In 2nd ACM SIGCOMM Workshop on Social Networks, '09. Google ScholarDigital Library
- V. D. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. J. Stat. Mech.: Theory and Experiment, '08.Google Scholar
Index Terms
- Overlapping communities in dynamic networks: their detection and mobile applications
Recommendations
WormTerminator: an effective containment of unknown and polymorphic fast spreading worms
ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systemsThe fast spreading worm is becoming one of the most serious threats to today's networked information systems. A fast spreading worm could infect hundreds of thousands of hosts within a few minutes. In order to stop a fast spreading worm, we need the ...
Algorithms and Applications for Community Detection in Weighted Networks
Community detection is an important issue due to its wide use in designing network protocols such as data forwarding in Delay Tolerant Networks (DTN) and worm containment in Online Social Networks (OSN). However, most of the existing community detection ...
A Host-Based Approach for Unknown Fast-Spreading Worm Detection and Containment
Special Section on Best Papers from SEAMS 2012The fast-spreading worm, which immediately propagates itself after a successful infection, is becoming one of the most serious threats to today’s networked information systems. In this article, we present WormTerminator, a host-based solution for fast ...
Comments