| dc.description.abstract | This paper presents a game-theoretic approach that models the formation of signed networks which contain both friendly and antagonistic relations. In our model, nodes have a plea- sure through their links to the others which is defined according to their triadic relations. They have a self centered goal based on the balance theory of signed networks: each node tries individually to minimize its stress from undesir- able relations with other nodes by maximizing the number of balanced triangles minus the number of unbalanced triangles she participates in. Since nodes act selfishly and don’t consider the social welfare, many theoretical problems about existence of the equilibrium, convergence and players’ interaction are raised and verified in this paper. We prove the NP-hardness of computing best-response and give an approximation for it by using quadratic programming and rounding its solution. We show that there is a tight relation between players’ best-responses. This result leads to a proof for convergence of the game. In addition, we report some experimental result on three online datasets. We show that as nodes play their best-response and time goes forward, the total pleasure of the network increases monotonically. Finally, we introduce a smartness factor for social media sites that helps people to measure the amount of deviation from best possible strategy and suggest a new model that is more adapted to these media. This measure can also be applied in the verification of all kinds of network formation games. | en_US |
