Distributed community detection in delay tolerant networks

ABSTRACT

Community is an important attribute of Pocket Switched Networks (PSN), because mobile devices are carried by people who tend to belong to communities. We analysed community structure from mobility traces and used for forwarding algorithms [12], which shows significant impact of community. Here, we propose and evaluate three novel distributed community detection approaches with great potential to detect both static and temporal communities. We find that with suitable configuration of the threshold values, the distributed community detection can approximate their corresponding centralised methods up to 90% accuracy.

REFERENCES

• 1: A. Chaintreau et al. Impact of human mobility on the design of opportunistic forwarding algorithms. In Proc. INFOCOM, April 2006.
• 2: A. Clauset. Finding local community structure in networks. Physical Review E, 72:026132, 2005.
• 3: L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas. Comparing community structure identification, 2005.
• 4: C. Diot et al. Haggle project, http://www.haggleproject.org, 2004.
• 5: Nathan Eagle , Alex (Sandy) Pentland, Reality mining: sensing complex social systems, Personal and Ubiquitous Computing, v.10 n.4, p.255-268, March 2006 [doi>10.1007/s00779-005-0046-3]
• 6: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 7: Gary William Flake , Steve Lawrence , C. Lee Giles , Frans M. Coetzee, Self-Organization and Identification of Web Communities, Computer, v.35 n.3, p.66-71, March 2002 [doi>10.1109/2.989932]
• 8: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 9: L. H. Hartwell, J. J. Hopfield, S. Leibler, and A. W. Murray. From molecular to modular cell biology. Nature, 402(6761 Suppl), December 1999.
• 10: Tristan Henderson , David Kotz , Ilya Abyzov, The changing usage of a mature campus-wide wireless network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023739]
• 11: P. Hui and J. Crowcroft. Bubble rap: Forwarding in small world dtns in ever decreasing circles. Technical Report UCAM-CL-TR-684, University of Cambridge, May 2007.
• 12: Pan Hui , Jon Crowcroft, How Small Labels Create Big Improvements, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.65-70, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.55]
• 13: M. E. J. Newman. Analysis of weighted networks. Physical Review E, 70:056131, 2004.
• 14: Evan P. C. Jones , Lily Li , Paul A. S. Ward, Practical routing in delay-tolerant networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.237-243, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080141]
• 15: J. Leguay et al. Evaluating mobility pattern space routing for DTNs. In Proc. INFOCOM, 2006.
• 16: Jérémie Leguay , Anders Lindgren , James Scott , Timur Friedman , Jon Crowcroft, Opportunistic content distribution in an urban setting, Proceedings of the 2006 SIGCOMM workshop on Challenged networks, p.205-212, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162654.1162657]
• 17: A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. In Proc. SAPIR, 2004.
• 18: D. Lusseau and M. E. J. Newman. Identifying the role that individual animals play in their social network. PROC. R. SOC. LONDON B, 271:S477, 2004.
• 19: Marvin McNett , Geoffrey M. Voelker, Access and mobility of wireless PDA users, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.2, April 2005 [doi>10.1145/1072989.1072995]
• 20: Mirco Musolesi , Stephen Hailes , Cecilia Mascolo, Adaptive Routing for Intermittently Connected Mobile Ad Hoc Networks, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.183-189, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.17]
• 21: M. Newman. Detecting community structure in networks. Eur. Phys. J. B, 38:321--330, 2004.
• 22: S. Okasha. Altruism, group selection and correlated interaction. British Journal for the Philosophy of Science, 56(4):703--725, December 2005.
• 23: G. Palla et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043):814--818, 2005.
• 24: P. Jaccard. Bulletin de la Societe Vaudoise des Sciences Naturelles, 37:547, 1901.
• 25: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 26: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, April 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
delay tolerant networks, distributed community detection, network measurement, social networks