Method for Identifying Node Dissemination Capability in Opportunistic Social Networks
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [17]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Although socially aware opportunistic communication paradigms are considered to have broad potential applications, very little is known about how the dynamic networks evolve and which nodes are more important both in sustaining the network topology and in forwarding or disseminating messages. Through the concept of walk and the adjacent matrix product of static graph theory, this paper extends a measurement, Katz Centrality (KC) that originated from Social Networks Analysis (SNA), to dynamic evolving opportunistic mobile networks. This is done in effort to examine the dissemination capabilities of different mobile nodes. The cornerstone of this method is the dynamics of an opportunistic contact network can be expressed through time-split observations, which result in a sequence of snapshots. By simply multiplying the adjacent matrix of each snapshot along the direction of time, the resulting matrix, in which the spatial and temporal dependency of the network are fully captured, can be obtained, so as to evaluate the relative information dissemination capability of each mobile node. The research uses two typical contact trace datasets for validation and the results show that several mobile nodes with the highest communicability identified by this method are more efficient in information dissemination than others in the whole network and can be chosen as good candidates when some interventions, such as accelerating or suppressing the speed of message dissemination in network, are required to be made on network.

    Reference
    [1] Xiong YP, Sun LM, Niu JW, Liu Y. Opportunistic networks. Journal of Software, 2009,20(1):124-137 (in Chinese with Englishabstract). http://www.jos.org.cn/1000-9825/3467.htm [doi: 10.3724/SP.J.1001.2009.03476]
    [2] Conti M, Giordano S, May M, Passarella A. From opportunistic networks to opportunistic computing. IEEE CommunicationsMagazine, 2010,48(9):126-139 [doi: 10.1109/MCOM.2010.5560597]
    [3] Newman MEJ. Networks: An Introduction. New York: Oxford University Press, 2010.
    [4] Avin C, Koucky M, Lotker Z. How to explore a fast-changing world. In: Proc. of the 35th Int’l Colloquium on Automata,Languages and Programming (ICALP). Reykjavik: ICE-TCS, 2008. 121-132 [doi: 10.1007/978-3-540-70575-8_11]
    [5] Scherrer A, Borgnat P, Fleury E, Guillaume JL, Robardet C. Description and simulation of dynamic mobility Networks. ComputerNetworks, 2008,52(15):2842-2858 [doi: 10.1016/j.comnet.2008.06.007]
    [6] Grindrod P, Higham DJ. Evolving graphs: Dynamical models, inverse problems and propagation. Proc. of the Royal Society A:Mathematical, Physical and Engineering Sciences, 2010,466(2115): 753-770 [doi: 10.1061/j.comnet.2008.06.077]
    [7] Casteigts A, Flocchini P, Quattrociocchi W, Santoro N. Time-Varying graphs and dynamic networks. In: Proc. of the 10th Int’lConf. on Adhoc Networks and Wireless (ADHOC-NOW). Paderborn, 2011. 346-359 [doi: 10.1080/17445760.2012.668546]
    [8] Santoro N, Quattrociocchi W, Flocchini P, Casteigts A, Amblard F. Time-Varying graphs and social network analysis: Temporalindicators and metrics. In: Proc. of the 3rd AISB Social Networks and Multiagent Systems Symp. (SNAMAS). York, 2011. 32-38.
    [9] Prakash BA, Tong H, Valler N, Faloutsos M, Faloutsos C. Virus propagation on time-varying networks: Theory and immunizationalgorithms. In: Proc. of the European Conf. on Machine Learning and Principles and Practice of Knowledge Discovery inDatabases (ECML/PKDD), PART III. Barcelona: Springer-Verlag, 2010. 99-114.
    [10] Tang J, Scellato S, Musolesi M, Mascolo C, Latora V. Small-World behavior in time-varying graphs. Physical Review E, 2010,81(5).
    [11] Yoneki E, Hui P, Crowcroft J. Wireless epidemic spread in dynamic human networks. In: Bio-Inspired Computing andCommunication. Springer-Verlag, 2008. 116-132. [doi: 10.1007/978-3-540-92191-2_11]
    [12] Grindrod P, Parson MC, Higham DJ, Parsons MC, Estrada E. Communicability across evolving networks. Physical Review E, 2011,83. [doi: 10.1103/PhysRevE.83.046120]
    [13] Jacquet P, Mans B, Rodolakis G. Information propagation speed in mobile and delay tolerant networks. IEEE Trans. onInformation Theory, 2010,56(10):5001-5015. [doi:10.1109/TIT.2010.2059830]
    [14] Tang J, Mascolo C, Musolesi M, Latora V. Exploiting temporal complex network metrics in mobile malware containment. In: Proc.of the 12th IEEE Int’l Symp. on a World of Wireless, Mobile and Multimedia Networks (WoWMoM 2011). Lucca: IEEE, 2011.1-9. [doi: 10.1109/WoWMoM.2011.5986463]
    [15] Nguyen NP, Dinh TN, Tokala S, Thai MT. Overlapping communities in dynamic networks: Their detection and mobileapplications. In: Proc. of the 17th Annual Int’l Conf. on Mobile Computing and Networking (MobiCom 2011). Las Vegas: ACM,2011. 85-96. [doi: 10.1145/2030613.2030624]
    [16] A community resource for archiving wireless data. http://crawdad.cs.dartmouth.edu/
    [17] Clauset A, Eagle N. Persistence and periodicity in a dynamic proximity network. In: Proc. of the DIMACS Workshop onComputational Methods for Dynamic Interaction Network. 2007.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

蔡青松,牛建伟,刘明珠.一种评估机会社会网络中节点消息传播能力的方法.软件学报,2012,23(zk1):49-58

Copy
Share
Article Metrics
  • Abstract:4417
  • PDF: 7713
  • HTML: 0
  • Cited by: 0
History
  • Received:May 05,2012
  • Revised:August 17,2012
  • Online: October 11,2012
You are the first2038312Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063