Discovering The Dynamics Of Social Networks And Distributed Search Strategies For Networked Environments

Social network,as one part of complex network,focuses on the research of behaviors of human being and organizations in society and abstracts them as a network structure with interactions among individuals.Social networks exist everywhere and show strong relationships with our daily life,such as actor collaboration network,scientist collaboration network,disease infection network,virtual community network,and so on.Analyzing the structures and properties of social networks would help us better understand social phenomena,and be of significance with decision-making,management and optimization problems in society.Traditional social network researches are usually analyze network structures in static view,such as degree distribution,average path length and clustering coefficient in networks.Nevertheless,real social networks are evolving systems.Internal individuals interact with each other and their relationships and properties are dynamic,so do network topology structures,capabilities,behaviors in networks.Recently,the dynamics of social networks are attached more and more importance.Carley presented a concept named as Dynamical Social Network and considered it as the most important property of social networks.What's more,she tried to establish an organized model to research features of information flow and decision-making flow in social networks.Comparing with external dynamic phenomena of social networks,we are more curious about the source of dynamics which is considered as Dynamics of Network Evolution.One objective of social network analysis is to understand relationships between different dynamics and topology structures in networks which are determined by forming styles and evolving mechanisms of networks.So researching the mechanism model of network evolution becomes a hot problem,which is also one of our task in this paper.Different from traditional methods,we analyzed the dynamics of individuals in social networks,and found that the properties of individuals decayed with time and could be strengthened again by external stimulations.We call this phenomenon the memory effect in social networks.The existence of memory effect is the internal reason of dynamics of network topologies and leads to the network evolutions.So we present a novel dynamic social network model:Social Memory Network(SMN),where the attraction of nodes decays with time and would be strengthened by new connections, the probability of a node being connected with a new link is proportional to its attraction. The established network contains not only the features of small-world and scale-free,but also the dynamic network topology structures which are more similar with networks in real world.We validated the model with real data and analyzed the influence of memory effect with network structures and capabilities.The SMN model degenerates to be BA model[35]when memory disappears(β=0).So SMN model can be considered as a more generalized one.Because of memory effect,the property such as hotness(stands for the attraction, influence,etc) of some nodes in a network would reach the peak values during a certain period.But in a long term view,these nodes with max hotness changes dynamically with time.These nodes have strong influence during certain period and play important roles in dynamics of network topologies and information circulations.We usually have to know the positions of these important nodes in applying and analyzing.The size of social networks are mostly very large.So how to find and track important nodes in such large dynamic networks would be another challenge.Address to this problem,we present distributed search methods based on Autonomy-Oriented Computing(AOC) to find and track important nodes in networks. Every agent in the method only searches in its local environment as an independent computing union.Agents interact with environments and other agents and approach global targets autonomously from local environments under the government of their global-directed behavior rules which is considered as strategy in this paper.We developed several search strategies based on AOC method,including three local moving search strategies,Levy Flight search strategy and Adaptive Probability search strategy. We analyzed the internal mechanisms of strategies and examined their search performance including search efficiency,robustness,scalability and time complexity.We examined strategies with a real network collected from USTC BBS.The results show that AOC-based search strategies can perform outstanding search effect in large-scale, dynamic and discrete environments.What's more,we designed three different artificial networks to examine the search strategies and also got good performance.So the search strategies can be generalized to normal environments and would have broad space for applications.