research-article

Understanding and modeling the small-world phenomenon in dynamic networks

Authors:

MSWiM '12: Proceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems

Pages 377 - 384

https://doi.org/10.1145/2387238.2387301

Published: 21 October 2012 Publication History

Get Access

Abstract

The small-world phenomenon first introduced in the context of static graphs consists of graphs with high clustering coefficient and low shortest path length. This is an intrinsic property of many real complex static networks. Recent research has shown that this structure is also observable in dynamic networks but how it emerges remains an open problem. In this paper, we propose a model capable of capturing the small-world behavior observed in various real traces. We then study information diffusion in such small-world networks. Analytical and simulation results with epidemic model show that the small-world structure increases dramatically the information spreading speed in dynamic networks.

References

[1]

Augustin Chaintreau, Pan Hui, Jon Crowcroft, Christophe Diot, Richard Gass, and James Scott. Impact of human mobility on opportunistic forwarding algorithms. IEEE Transactions on Mobile Computing, 6(6):606--620, June 2007.

Digital Library

Google Scholar

[2]

Aaron Clauset and Nathan Eagle. Persistence and periodicity in a dynamic proximity network. In DIMACS/DyDAn Workshop on Computational Methods for Dynamic Interaction Networks, 2007.

Google Scholar

[3]

JM Kleinberg. Navigation in a small world. Nature, 406(6798):845, August 2000.

Crossref

Google Scholar

[4]

Jérémie Leguay, Anders Lindgren, James Scott, Timur Friedman, and Jon Crowcroft. Opportunistic content distribution in an urban setting. In Proceedings of the 2006 SIGCOMM workshop on Challenged networks - CHANTS '06, pages 205--212, New York, New York, USA, September 2006. ACM Press.

Digital Library

Google Scholar

[5]

M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Review, 45(2):167, November 2003.

Digital Library

Google Scholar

[6]

MEJ Newman. Networks: an introduction. Oxford University Press, 2010.

Digital Library

Google Scholar

[7]

A.D. Nguyen, Patrick Sénac, Victor Ramiro, and Michel Diaz. STEPS-an approach for human mobility modeling. In NETWORKING 2011, pages 254--265. Springer, 2011.

Crossref

Google Scholar

[8]

John Tang, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. Temporal distance metrics for social network analysis. In Proceedings of the 2nd ACM workshop on Online social networks - WOSN '09, page 31, New York, New York, USA, August 2009. ACM Press.

Digital Library

Google Scholar

[9]

John Tang, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. Characterising temporal distance and reachability in mobile and online social networks. ACM SIGCOMM Computer Communication Review, 40(1):118--124, January 2010.

Digital Library

Google Scholar

[10]

D.J. Watts and S.H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):440--442, June 1998.

Crossref

Google Scholar

Cited By

View all

Doostmohammadian MZarrabi HDoustmohammadian ARabiee H(2023)Infection curve flattening via targeted interventions and self-isolationSocial Network Analysis and Mining10.1007/s13278-023-01141-513:1Online publication date: 16-Oct-2023
https://doi.org/10.1007/s13278-023-01141-5
(2018)Impact of overlapping in the radio coverage areas Of multiple Wi-Fi access points on detecting encountersJournal of Electronics and Sensors10.31829/2689-6958/jes2018-1(1)-103(1-18)Online publication date: 9-Jun-2018
https://doi.org/10.31829/2689-6958/jes2018-1(1)-103
Ren SLi JTaya FdeSouza JThakor NBezerianos A(2017)Dynamic Functional Segregation and Integration in Human Brain Network During Complex TasksIEEE Transactions on Neural Systems and Rehabilitation Engineering10.1109/TNSRE.2016.259796125:6(547-556)Online publication date: Jun-2017
https://doi.org/10.1109/TNSRE.2016.2597961
Show More Cited By

Index Terms

Understanding and modeling the small-world phenomenon in dynamic networks

Recommendations

Small-World Network in OMNeT++
ISMS '12: Proceedings of the 2012 Third International Conference on Intelligent Systems Modelling and Simulation

The small-world phenomenon describes the behavior of very large networks with a relatively small number of hops between any two nodes. The main characteristics of such networks are small average path length (L) and large clustering coefficient (C). In ...
Centrality metric for dynamic networks
MLG '10: Proceedings of the Eighth Workshop on Mining and Learning with Graphs

Centrality is an important notion in network analysis and is used to measure the degree to which network structure contributes to the importance of a node in a network. While many different centrality measures exist, most of them apply to static ...
Small-world phenomenon of keywords network based on complex network

Based on the network comprised of 111,444 keywords of library and information science that are extracted from Scopus, and taken into consideration the major properties of average distance and clustering coefficients, the present authors, with the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MSWiM '12: Proceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems

October 2012

428 pages

ISBN:9781450316286

DOI:10.1145/2387238

General Chair:
Albert Zomaya
University of Sydney, Australia
,
Program Chairs:
Bjorn Landfeldt
Lund University, Sweden
,
Ravi Prakash
University of Texas at Austin, USA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MSWiM '12

Sponsor:

SIGSIM

MSWiM '12: The 15th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems

October 21 - 25, 2012

Paphos, Cyprus

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
317
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)7

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Doostmohammadian MZarrabi HDoustmohammadian ARabiee H(2023)Infection curve flattening via targeted interventions and self-isolationSocial Network Analysis and Mining10.1007/s13278-023-01141-513:1Online publication date: 16-Oct-2023
https://doi.org/10.1007/s13278-023-01141-5
(2018)Impact of overlapping in the radio coverage areas Of multiple Wi-Fi access points on detecting encountersJournal of Electronics and Sensors10.31829/2689-6958/jes2018-1(1)-103(1-18)Online publication date: 9-Jun-2018
https://doi.org/10.31829/2689-6958/jes2018-1(1)-103
Ren SLi JTaya FdeSouza JThakor NBezerianos A(2017)Dynamic Functional Segregation and Integration in Human Brain Network During Complex TasksIEEE Transactions on Neural Systems and Rehabilitation Engineering10.1109/TNSRE.2016.259796125:6(547-556)Online publication date: Jun-2017
https://doi.org/10.1109/TNSRE.2016.2597961
Sarkar RRasul KChakrabarty A(2015)Survey on Routing in Pocket Switched NetworkWireless Sensor Network10.4236/wsn.2015.7901007:09(113-128)Online publication date: 2015
https://doi.org/10.4236/wsn.2015.79010
Wei KGuo SZeng DXu KLi K(2015)Exploiting Small World Properties for Message Forwarding in Delay Tolerant NetworksIEEE Transactions on Computers10.1109/TC.2015.238980764:10(2809-2818)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1109/TC.2015.2389807
Nguyen ASenac PDiaz MWu JWang Y(2014)Behavioral and Structural Analysis of Mobile Cloud Opportunistic NetworksOpportunistic Mobile Social Networks10.1201/b17231-6(123-159)Online publication date: 17-Jul-2014
https://doi.org/10.1201/b17231-6
Nguyen ASenac PDiaz MCerqueira EMauthe ACurado MLeszczuk MBoavida FLua E(2013)How disorder impacts routing in human-centric disruption tolerant networksProceedings of the 2013 ACM SIGCOMM workshop on Future human-centric multimedia networking10.1145/2491172.2491178(47-52)Online publication date: 16-Aug-2013
https://dl.acm.org/doi/10.1145/2491172.2491178
Anh-Dung Nguyen Senac PDiaz M(2013)On the impact of disorder on dynamic network navigation2013 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)10.1109/INFCOMW.2013.6562854(83-84)Online publication date: Apr-2013
https://doi.org/10.1109/INFCOMW.2013.6562854
Anh-Dung Nguyen Senac PDiaz M(2013)On the impact of disorder on dynamic network navigation2013 Proceedings IEEE INFOCOM10.1109/INFCOM.2013.6566724(17-18)Online publication date: Apr-2013
https://doi.org/10.1109/INFCOM.2013.6566724

View Options

Login options

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

Cited By

Index Terms

Recommendations

Small-World Network in OMNeT++

Centrality metric for dynamic networks

Small-world phenomenon of keywords network based on complex network