Research On The Structure, Evolution And Dynamics Of Online Social Networks

The rise and development of social network analysis in the last century furthered the comprehension for extremely complex social systems. In recent years, with the development of information technology and the broad application of Web 2.0 framework, many online social networks emerge in the Internet. The sizes of the networks are extraordinarily large and their structures always evolve over time, thus only the integration of traditional social network theory and modern complex network research can help to understand the patterns and dynamical processes in the interactions among people. Recently the structure of online social networks and the dynamical processes on them have attracted attentions of researchers from different disciplines.The research on relations among individuals in Web communities and human online behaviors has become a hot topic in the field of information science. The relations and interactions among people in the Internet can be well described by online social networks. The paper focuses on the structure, evolution and opinion dynamics of online social networks, besides the paper contributes a new topological parameter characterizing the structure of complex networks-heterogeneity index, and also studies the statistical feature of individual activity and popularity in online social systems, and the influencing factors.The main content and contributions of this dissertation are summarized as follows:1. The thesis brings forward a novel topological metric-heterogeneity index 0≤H< 1 which can quantify the degree heterogeneity of any given network, including regular networks, random graphs, small-world networks, exponential networks and power law networks. The heterogeneity index of a completely homogeneous network is 0; however, the heterogeneity index of a completely heterogeneous network will approach 1. We analytically study the degree heterogeneity of exponential networks and find the existence of an upper bound of H = 0.5 for such networks. We also analytically study the degree heterogeneity of power law networks and find that for an infinite power law network, H > 0.5 only if its degree exponentγ∈(1, 2.5) and H→1 only ifγ∈(1, 2]. We further prove that for any power law network withγ> 2.5, there always exists an exponential network such that both networks have the same heterogeneity index.2. We study the structural characteristics of a large online social network Wealink. Compared with real social networks, it shows some common features, such as small-world, large clustering coefficient, hierarchical structure and community property. However, this network also shows its own specialties, such as scale-freeness, sawtooth shape in the distributions of connected subgraph size, degree and community size, and most significantly, degree disassortativity. The functions of networks have distinct influence on structures; we illuminate the mechanisms for the formation of degree distribution of the network by a realistic model and discuss the origin of degree disassortativity in online social networks.3. Further we study the structural evolution of Wealink. We find that its scale growth shows non-trivial S shape which may provide the first exemplification for Bass diffusion model in Web communities and predict the life cycle of online social networks to some extent. We reveal that, different from the predicted by the traditional network growth models, the evolutions of many network properties, such as density, clustering, heterogeneity and modularity, show non-monotone feature, and shrink phenomenon occurs for the path length and diameter of the network. Especially Wealink undergoes a transition from degree assortativity to disassortativity. To the best of our knowledge, this is the first real-world network observed which possesses the intriguing feature. We propose a network model which can reasonably elucidate the transition. 4. We also study the user behaviors in Wealink. We find that link requests are quickly reciprocated and the distribution of intervals between launching and accepting link requests decays in an exponential form. Besides the degrees of inviters/accepters are almost irrelevant to reciprocation time. The distributions of intervals of user behaviors, such as launching or accepting link requests, follow power law with a universal exponent. We also study the preferential linking phenomena of the network and find that linear preference holds for all three cases: preferential acceptance, creation and attachment, which can predict the behaviors of linking between users effectively.5. We study individual activity and popularity in online social systems. Empirical research finds that the distribution of activity and popularity follows power law or stretched exponential and activity has distinct influence on human dynamics, i.e. from low-activity to high-activity users, the distributions of intervals of user behaviors get more and more centralized, which denies the validity of universality classes in human dynamics proposed by Barabási et al. We bring forward a probability model which can elucidate the mechanism leading to different distributions of activity and popularity and find that, when preference metricβ= 1, i.e. linear preference, the distributions are power law; when 0 <β< 1, i.e. sub-linear preference, the distributions are stretched exponential; whereas whenβ= 0, i.e. without preference, the distributions are reduced to exponential.6. Finally we study the discrete state opinion dynamics on social networks based on social influence. Initially the state of each agent can take discrete values i = 1,2,…,I. We find that for any I≥2 and self-confidence parameter, i.e. agents'probabilities of maintaining current states 0≤u< 1, when u is a degree-independent constant, the weighted proportion of the population that hold a given state i is a martingale, i.e. the mean values of the fractions q_i of total degree of agents with state i in the total degree of the whole network are a constant, and the fraction q_i of state i will gradually converge to . The tendency can slow down with the increase of degree assortativity of networks. When u is degree dependent, does not possess the martingale property, however q_i still converges to it. In both cases for a finite network the states of all agents will finally reach consensus. Further we study the case where there exist stubborn persons in the population whose states do not change over time. We find that for degree-independent constant u , both q_i and will converge to fixed proportions which only depend on the distribution of initial obstinate persons, and naturally the final equilibrium state will be the coexistence of diverse states held by the stubborn people. The analytical results are verified by numerical simulations on Barabási-Albert networks. The model highlights the influence of high-degree agents on the final consensus or coexistence state and captures some realistic features of the diffusion of opinions in social networks.