More Web Proxy on the site http://driver.im/

research-article

Distributed community detection in delay tolerant networks

Authors:

Jon CrowcroftAuthors Info & Claims

MobiArch '07: Proceedings of 2nd ACM/IEEE international workshop on Mobility in the evolving internet architecture

Article No.: 7, Pages 1 - 8

https://doi.org/10.1145/1366919.1366929

Published: 27 August 2007 Publication History

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]

N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, V10(4):255--268, May 2006.

Digital Library

[6]

K. Fall. A delay-tolerant network architecture for challenged internets. In Proc. SIGCOMM, 2003.

Digital Library

[7]

G. W. Flake, S. Lawrence, C. L. Giles, and F. Coetzee. Self-organization of the web and identification of communities. IEEE Computer, 35(3):66--71, 2002.

Digital Library

[8]

M. Grossglauser and D. Tse. Mobility increases the capacity of ad-hoc wireless networks. Transactions on Networking, 10(4):477--486, August 2002.

Digital Library

[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]

T. Henderson, D. Kotz, and I. Abyzov. The changing usage of a mature campus-wide wireless network. In Proc. Mobicom, 2004.

Digital Library

[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]

P. Hui and J. Crowcroft. How small lables create big improvements. In Proc. IEEE ICMAN, March 2007.

Digital Library

[13]

M. E. J. Newman. Analysis of weighted networks. Physical Review E, 70:056131, 2004.

[14]

E. P. C. Jones, L. Li, and P. A. S. Ward. Practical routing in delay-tolerant networks. In Proc. WDTN, 2005.

Digital Library

[15]

J. Leguay et al. Evaluating mobility pattern space routing for DTNs. In Proc. INFOCOM, 2006.

[16]

J. Leguay et al. Opportunistic content distribution in an urban setting. In ACM CHANTS, 2006.

Digital Library

[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]

M. Mcnett and G. M. Voelker. Access and mobility of wireless pda users. SIGMOBILE Mob. Comput. Commun. Rev., 9(2):40--55, April 2005.

Digital Library

[20]

M. Musolesi, S. Hailes, and C. Mascolo. Adaptive routing for intermittently connected mobile ad hoc networks. In Proc. WOWMOM, 2005.

Digital Library

[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]

T. Spyropoulos, K. Psounis, and C. Raghavendra. Spray and wait: An efficient routing scheme for intermittently connected mobile networks. In Proc. WDTN, 2005.

Digital Library

[26]

A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, April 2000.

Cited By

Singh RKumar BAhmad M(2024)A Hybrid Routing Protocol to Establish Communication in Mobility Cast Using Mobility PatternWireless Personal Communications10.1007/s11277-024-11081-8135:2(875-898)Online publication date: 2-May-2024
https://doi.org/10.1007/s11277-024-11081-8
Papei HLi Y(2023)Stochastic Local Community Detection in NetworksAlgorithms10.3390/a1601002216:1(22)Online publication date: 1-Jan-2023
https://doi.org/10.3390/a16010022
Jesús-Azabal MGarcía-Alonso JSoares VGalán-Jiménez J(2022)Improving Delivery Probability in Mobile Opportunistic Networks with Social-Based RoutingElectronics10.3390/electronics1113208411:13(2084)Online publication date: 2-Jul-2022
https://doi.org/10.3390/electronics11132084
Show More Cited By

Index Terms

Distributed community detection in delay tolerant networks

Recommendations

Visualizing community detection in opportunistic networks
CHANTS '07: Proceedings of the second ACM workshop on Challenged networks

Community is an important attribute of Pocket Switched Networks (PSNs), since mobile devices are carried by people who tend to belong to communities in their social life. We discover the heterogeneity of human interactions such as community formation ...
An evidential influence-based label propagation algorithm for distributed community detection in social networks

Community detection in social networks is a computationally challenging task that has attracted many researchers in the last decade. Most of approaches in the literature focus only on modeling structural properties, ignoring the social aspect in the ...
A socio-aware overlay for publish/subscribe communication in delay tolerant networks
MSWiM '07: Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems

The emergence of Delay Tolerant Networks (DTNs) has culminated in a new generation of wireless networking. We focus on a type of human-to-human communication in DTNs, where human behaviour exhibits the characteristics of networks by forming a community. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiArch '07: Proceedings of 2nd ACM/IEEE international workshop on Mobility in the evolving internet architecture

August 2007

85 pages

ISBN:9781595937841

DOI:10.1145/1366919

Program Chairs:
Xiaoming Fu
University of Goettingen, Germany
,
Katherine Guo
Bell Laboratories
,
Sue Moon
KAIST, Korea
,
Ryuji Wakikawa
Keio University, Japan

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiArch07

Sponsor:

SIGCOMM

MobiArch07: Second International Workshop on Mobility in the Evolving Internet Architecture

August 27 - 30, 2007

Kyoto, Japan

Acceptance Rates

Overall Acceptance Rate 47 of 92 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

266
Total Citations
View Citations
1,739
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Singh RKumar BAhmad M(2024)A Hybrid Routing Protocol to Establish Communication in Mobility Cast Using Mobility PatternWireless Personal Communications10.1007/s11277-024-11081-8135:2(875-898)Online publication date: 2-May-2024
https://doi.org/10.1007/s11277-024-11081-8
Papei HLi Y(2023)Stochastic Local Community Detection in NetworksAlgorithms10.3390/a1601002216:1(22)Online publication date: 1-Jan-2023
https://doi.org/10.3390/a16010022
Jesús-Azabal MGarcía-Alonso JSoares VGalán-Jiménez J(2022)Improving Delivery Probability in Mobile Opportunistic Networks with Social-Based RoutingElectronics10.3390/electronics1113208411:13(2084)Online publication date: 2-Jul-2022
https://doi.org/10.3390/electronics11132084
Soelistijanto BAyu V(2022)Improving Traffic Load Distribution Fairness in Mobile Social NetworksAlgorithms10.3390/a1507022215:7(222)Online publication date: 22-Jun-2022
https://doi.org/10.3390/a15070222
Papapetrou ELikas A(2022)A replication strategy for mobile opportunistic networks based on utility clusteringAd Hoc Networks10.1016/j.adhoc.2021.102738125:COnline publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1016/j.adhoc.2021.102738
Guidi BMichienzi ARicci L(2022)Managing communities in decentralised social environmentsPeer-to-Peer Networking and Applications10.1007/s12083-022-01358-915:5(2404-2429)Online publication date: 22-Jul-2022
https://doi.org/10.1007/s12083-022-01358-9
Ye ZZhou Q(2021)Performance Evaluation Indicators of Space Dynamic Networks under Broadcast MechanismSpace: Science & Technology10.34133/2021/98265172021Online publication date: Jan-2021
https://doi.org/10.34133/2021/9826517
Manole ACiobanu RDobre CPurnichescu-Purtan R(2021)Opportunistic Network Algorithms for Internet Traffic Offloading in Music Festival ScenariosSensors10.3390/s2110331521:10(3315)Online publication date: 11-May-2021
https://doi.org/10.3390/s21103315
Li ZYang XJiang C(2021)Tree-searching based trust assessment through communities in vehicular networksPeer-to-Peer Networking and Applications10.1007/s12083-021-01114-5Online publication date: 23-Mar-2021
https://doi.org/10.1007/s12083-021-01114-5
Manghiuc B(2021)Distributed Detection of Clusters of Arbitrary SizeStructural Information and Communication Complexity10.1007/978-3-030-79527-6_21(370-387)Online publication date: 20-Jun-2021
https://doi.org/10.1007/978-3-030-79527-6_21
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents