Autonomy-Oriented Search in Dynamic Community Networks: A Case Study in Decentralized Network Immunization

• Autorzy: Liu J. , Gao C. , Zhong N.
• Języki publikacji: EN

Abstrakty

EN

In recent years, immunization strategies have been developed for stopping epidemics in complex-network-like environments. Yet it still remains a challenge for existing strategies to deal with dynamically-evolving networks that contain community structures, though they are ubiquitous in the real world. In this paper, we examine the performances of an autonomy-oriented distributed search strategy for tackling such networks. The strategy is based on the ideas of self-organization and positive feedback from Autonomy-Oriented Computing (AOC). Our experimental results have shown that autonomous entities in this strategy can collectively find and immunize most highly-connected nodes in a dynamic, community-based network within a few steps.

Słowa kluczowe

EN

autonomy-oriented computing; complex networks; immunization strategy; self-organization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 2
• Strony: 207--226
• Opis fizyczny: Bibliogr. 35 poz. wykr.

Twórcy

autor

Liu J.

autor

Gao C.

autor

Zhong N.

Bibliografia

• [1] Liu, J.: Web Intelligence (WI): What makes Wisdom Web? (Invited Talk), In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03) (G. Gottlob, T. Walsh, Eds.), Morgan Kaufmann Publishers, Acapulco 2003, 1596-1601.
• [2] Zhong, N., Liu, J., Yao, Y.Y.: Envisioning intelligent information technologies (iIT) from the stand-point of Web Intelligence (WI), Communications of the ACM, 50(3), 2007, 89-94.
• [3] Dezso, Z., Barabasi, A.-L.: Halting viruses in scale-free networks, Physical Review E, 65(5), 2002, 055103.
• [4] Chen, Y., Paul, G., Havlin, S., Liljeros, F., Stanley, H.E.: Finding a better immunization strategy, Physical Review Letter, 101(5), 2008, 058701.
• [5] Liu, J., Jin, X., Tsui, K.C.: Autonomy Oriented Computing (AOC): From Problem Solving to Complex Systems Modeling, Kluwer Academic Publishers/Springer, Boston, 2005.
• [6] Liu, J., Jin, X., Tsui, K.C.: Autonomy Oriented Computing (AOC): Formulating computational systems with autonomous components, IEEE Transactions on Systems, Man, and Cybernetics, Part A, 35(6), 2005, 879-902.
• [7] Liu, J.: Autonomy Oriented Computing (AOC): The nature and implications of a paradigmfor self-organized computing (Keynote Talk), In: Proceedings of the 4th International Conference on Natural Computation (ICNC'08) and the 5th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD'08) (M.Z. Guo, L. Zhao, L.P. Wang, Eds.), IEEE Communication Society, Jinan 2008, 3-11.
• [8] Zou, C.C., Towsley, D., Gong,W.: Modeling and simulation study of the propagation and defense of internet e-mail worms, IEEE Transaction on Dependable and Secure Computing, 4(2), 2007, 105-118.
• [9] Liu, J., Han, J., Tang, Y.Y.: Multi-agent oriented constraint satisfaction, Artificial Intelligence, 136(1), 2002, 101-144.
• [10] Xie, X.F., Liu, J.: Multiagent optimization system for solving the traveling salesman problem (TSP), IEEE Transactions on Systems, Man, and Cybernetics, Part B, 39(2), 2009, 489-502.
• [11] Yang, B., Liu, J.: Discovering global network communities based on local centralities, ACM Transactions on the Web, 2(1), 2008, 1-32.
• [12] Liu, J., Zhang, S., Yang, J.: Characterizing Web usage regularities with information foraging agents, IEEE Transactions on Knowledge and Data Engineering, 16(5), 2004, 566-584.
• [13] Liu, J., Tsui, K.C.: Toward nature-inspired computing, Communications of the ACM, 49(10), 2006, 59-64.
• [14] Liu, J., Gao, C., Zhong, N.: An autonomy-oriented paradigm for self-organized computing, In: 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technologies (R. Baeza-Yates, J. Lang, S. Mitra, S. Parsons, G. Pasi, Eds.), IEEE Communication Society, Milan 2009, 100-103.
• [15] Cohen, R., Havlin, S., Ben-Averaham, D.: Efficient immunization strategies for computer networks and populations, Physical Review Letter, 91(24), 2003, 247901.
• [16] Holme, P.: Efficient local strategies for vaccination and network attack, Europhysics Letters, 68(6), 2004, 908-914.
• [17] Gallos, L.K., Liljeros, F., Argyrakis, P., Bunde, A., Havlin, S.: Improving immunization strategies, Physical Review Letter, 75(4), 2007, 045104.
• [18] Echenique, P., Gomez-Gardenes, J., Moreno, Y., Vazquez, A.: Distance-d covering problem in scale-free networks with degree correlation, Physical Review E, 71(3), 2005, 035102.
• [19] Liu, J., Gao, C., Zhong, N.: A distributed immunization strategy based on autonomy-oriented computing, In: The 18th International Symposium on Methodologies for Intelligent Systems (ISMIS'09) (J. Rauch, Z.W. Ras, P. Berka, T. Elomaa, Eds.), LNCS 5722, Springer, Prague 2009, 503-512.
• [20] Kalogeraki, V., Gunopulos, D., Zeinalipour-Yazti, D.: A local search mechanism for peer-to-peer networks, In: Proceedings of the eleventh international conference on information and knowledge management (CIKM'02) (K. Kalpakis, N. Goharian, D. Grossman, Eds.), ACM Press, McLean 2002, 300-307.
• [21] Beraldi, R.: Random walk with long jumps for wireless ad hoc networks, Ad Hoc Networks, 7(2), 2009, 294-306.
• [22] Adamic, L.A., Lukose, R.M., Puniyani, A.R.: Search in power-law networks, Physical Review E, 64(4), 2001, 046135.
• [23] Forestiero, A., Mastroianni, C., Spezzano, G.: So-Grid: A self-organizing grid featuring bio-inspired algorithms, ACM Transactions on Autonomous and Adaptive System, 3(2), 2008, 1-37.
• [24] Sycara, K., Roth, S., Sadeh, N., Fox, M.: Distributed constrained heuristic search, IEEE Transactions on System, Man and Cybernetics, 21(6), 1991, 1446-1461.
• [25] Pastor-Satorras, R., Vespignani, A.: Epidemic spreading in scale-free networks, Physical Review Letters, 86(14), 2001, 3200-3203.
• [26] Liu, J., Gao, C., Zhong, N.: Virus propagation and immunization strategies in email networks, In: The InternationalConference on AdvancedDataMining and Applications (ADMA'09) (R. Huang, Q. Yang, J. Pei, J. Gama, X.F. Meng, X. Li, Eds.), LNCS 5678, Springer, Beijing 2009, 222-233.
• [27] Lloyd, A.L.,May, R.M.: How viruses spread among computers and people, Science, 292(5520), 2001, 1316-1317.
• [28] Meshkova, E., Riihijarvi, J., Petrova,M., Petri,M.: A survey on resource discoverymechanisms, peer-to-peer and service discovery frameworks, Computer Networks, 52(11), 2008, 2097-2128.
• [29] Mengshoel, O.J.: Understanding the role of noise in stochastic local search: Analysis and experiments, Artificial Intelligence, 72(8-9), 2008, 955-990.
• [30] Zhong, M., Shen, K., Seiferas, J.: The convergence-guaranteed random walk and its applications in peer-topeer networks, IEEE Transactions on Computers, 57(5), 2008, 619-633.
• [31] Bonabeau, E.: Editor's introduction: stigmergy, Artificial Life, 5(2), 1999, 95-96.
• [32] Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks, Nature, 393(6684), 1998, 440-442.
• [33] Fouss, F., Pirotte, A., Renders, J.M., Saerens, M.: Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation, IEEE Transactions on Knowledge and Data Engineering, 19(3), 2007, 355-369.
• [34] Strogatz, S.H.: Exploring complex networks, Nature, 410(6825), 2001, 268-276.
• [35] Bu, T., Towsley, D.: On distinguishing between internet power law topology generators, In: The 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'02) (D. Lee, A. Orda, Eds.), IEEE Communication Society, New York 2002, 638-647.