Show simple item record

dc.contributor.authorMALEKZADEH, Men_US
dc.contributor.authorFazli, Men_US
dc.contributor.authorJalaly Khalilabadi, Pen_US
dc.contributor.authorRabiee, HRen_US
dc.contributor.authorSafari, MAen_US
dc.contributor.author5th SNA-KDD Workshop ’11 (SNA-KDD’11)en_US
dc.description.abstractThis 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
dc.titleSocial balance and signed network formation gamesen_US
dc.typeConference Proceeding
dc.rights.holder© ACM

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record