Analysis And Optimization Of Competitive Dynamics In Complex Networks

The study of opinion formation and evolution in complex social networks has a long history,and gradually leads to an interdiscipline research direction—Opinion Dy-namics.A variety of mathematical models which capture certain characteristics of the real-world opinion formation and evolution are proposed in the literature.A focal topic in the research community is that how the mutual agreement among the individuals is achieved.Besides the widespread cooperative behavior,competition is also ubiquitous in our society,which,however,has not received due attention until most recently.This dissertation first surveys the recent advances in the study on competitive dynamics in complex networks and then proposes a competition model based on the continuous opinion formation process.After validating its rationality,we further investigate the competition characteristics,optimal competition strategies,and some extensions of this model.The main work can be summarized as follows:1.A continuous-state competition model is proposed.In this model two competi-tors have fixed and opposite states,and each normal agent adjusts its state according to a distributed consensus protocol.The state of each normal agent converges to a steady value which is determined by the network structure and the positions of competitors in the network.The model perfectly reproduces the splitting result of the karate club network.Furthermore,we compute an Influence Matrix(IM)based on the network structure,and construct a corresponding criterion to predict the bias of each normal agent and thus predict the competition result.Several criteria based on node centrality measurements are also proposed and compared by simulations using real world net-work data.2.An asynchronous competitive optimization problem is studied.Special atten-tion is paid to investigate how a competitor optimizes its utility by adding links to the network,under the condition that the strategy of its opponent is already known.T-wo definitions of competitiveness are defined in different competition situations,and hence lead to two competitive optimization problems.The computational complexity of the proposed problems is studied,and the monotonicity and the sub-modularity of the two objective functions are analyzed.The optimal solutions in several special net-works are obtained.For normal networks,three optimization algorithms and several centrality based heuristic algorithms are proposed according to the characteristics of the two problems.All algorithms are compared by simulations.3.A synchronous competitive optimization problem is studied.We focus on find-ing the optimal link-adding strategy of the competitor to maximize its utility without knowing the strategy of its opponent.Several centrality-based link-adding strategies are proposed.Simulations on continuous-state competition model show that the effec-tiveness of these centrality-based strategies relies on the network structure and positions of competitors.While for discrete-state competition model,there is a preferential or-der among the proposed centrality-based strategies.More precisely,the strategy based on betweenness centrality performs better than other strategies,and the superiority be-comes more apparent as the heterogeneity of network increase.4.Two extensions of the basic competition model are proposed:competition model with two sets of competitors and competition model with multiple competitors.In the competition model with two sets of competitors,by viewing the two sets of competitors as two super competitor,the network can be reconstructed and the mod-el is degenerated to the competition model with two competitors.The criteria based on IM and centralities measurements are modified to apply to this situation,and their effectiveness is verified by simulations.In the competition model with multiple com-petitors,to define the symmetrical and contrary multiple competitors,the state space is extended from one dimension to two dimension.The stability of system is proved and steady states of normal agents are computed,based on which the normal agent's bias and competition result are defined.Simulations show the performance of the cor-respondingly modified criteria based on IM and centrality measurements.Finally,we treat adding a competitor as a strategy of improving competitiveness and compare its performance with the strategy of adding edges.