Sunday, February 28, 2010

The hate and love relationships on social networks...

I had recently the "joy" of reading a very interesting articled by Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. And since it's a lazy sunday afternoon,I thought I might take the time to comment on my readings. The paper is titled "Signed Networks in Social Media", and this paper studies how the interaction between positive and negative relationships affects the structure of online social networks. They considered that the richness of a social network consists of a mixture of both positive and negative interactions that co-exist in one single structure.
It might be difficult to understand at first what a negative or a positive relationship in a social network is, since the vast majority of social networks only allow for positive relationships. Facebook for example, only permits users to designate who their friends are and state that they like the activity, status, picture etc of an individual. A user for example, is not capable of showing his dislike for another person's activity.
The study they carried out was therefore focused on social networks that do allow for positive and negative relationships.They obtained large-scale datasets from social applications where the sign of each link-positive or negative- could be reliably obtained.The social networks that were studied are:
  • Epinions: an online rating site that lets people give both positive and negative ratings not only on items but also to other raters. It basically has Web of Trust per User: A network of reviewers whose reviews and ratings the user has consistently found to be valuable. It also has a Block List: list of authors whose reviews the user did not find valuable. “... If you encounter a member whose reviews are consistently offensive, inaccurate, or otherwise low quality, you can add that member to your Block List...”

  • Slashdot: An online discussion site that allows users to tag other users as "friends" or "foes". The user can observe the different kind of relationships it holds with each different user. So if a person were to add someone as a friend, he/she would view them as a friend-> While if you add a user as a foe, you view them as a foe.
    If a user adds you as their friend, you would view them as a fan
    If a user adds you as your foe, you would view them as a freak.

  • Votes for Wikipedia admin candidate:When a Wikipedia user is considered for a promotion to the status of an admin, the community is able to cast public votes in favor of or against the promotion of this admin candidate. A positive vote is taken as a positive link from the voter to the candidate, and a negative vote as a negative link.

    This paper worked with the 3 datasets stated above and used these datasets along with 2 different theories of signed networks to reason about how different patterns of positive and negative links provide evidence of the different kind of relationships that exist across these networks. The 2 different theories of signed network that were used are:

    Structural Balance Theory: This was a theory that was proposed by Heider (1958) . Balance theory deals with three kinds of entities. The person (P) whose subjective environment we are concerned with, another person (O); and the object (X), which may be a third person.

Balance theory proposes that with three entities, person-another person-object (POX), three sets of relations exist i.e. between P and O; between P and X and; between O and X
Each of the three relations, P-O, P-X and O-X, can have one of two values. You can either 'like' (+) or 'dislike' (-). With three sets of possible relationships, each taking on one of two values (+/-) eight possible states of affairs exist. This theory states that balance state occurs when all sign multiplication of its sentiment relation charges positive.
For example, take the following diagram:

Here we have P, who we can name Pete that likes O, who we will call Olivia. Pete happens to hate hot peppers and chocolate, X. Balance Theory says, that for the relationship of these 3 individuals to be balanced, Olivia would also need to hate hot peppers and chocolate.
Some of the basic guidlines that Balance Theory follows are:
my friend’s friend is my friend
my friend’s enemy is my enemy
my enemy’s friend is my enemy
my enemy’s enemy is my friend

Now, for this paper they started analysis the social networks mentioned above, by comparing if these networks effectively followed the theorems of Balance theory , in this first stage they only considered undirected relationships between individuals, ie they only considered that Pete likes Olivia, but they did not consider whether or not Olivia likes or dislikes Pete. To carry out the comparative,the frequencies of different types of signed triads were taken into account.
They stated that a certain triad was overrepresented when the following occurred:
p(Ti ) larger than p0 (Ti )
Where P(Ti) represents the fractions of triads Ti. (Ti represents the number of triads of type Ti, for example it could represent the number of 3 person relationships whose edges are all POSITIVE) And P0(Ti) is the apriori probability of Ti based on sign distribution.
They also stated that a certain triad was underrepresented,
if p(Ti )less than po(ti) .
They saw that using status theory they were here able to explain much better these social interactions.
Status theory, claims the following:
Considering nodes A and B, a positive edge from A to B means: “I think B has higher status than I (A) do” A negative edge from A to B means: “I think B has lower status than I (A) do”
Thus, the theory of status predicts that if A links positive to B, then “A regards B as having higher status and" and if B links positive to C then " B regards C as having higher status – so C should regard A as having low status and hence be inclined to link negatively to A

The following table presents their findings:

ti referes to the selected triad. count refers to the number of times that particular triad was encountered in the network. P (+): prob. that closing red edge is positive;SG: surprise of edge initiator giving a positive edge (This is, surprise that Pete would give a positive link to Olivia);Sr: surprise of edge destination receiving a positive edge (surprise that Olivia would get a positive link);Bg:consistency of balance theory with generative surprise;
Br: consistency of balance with receptive surprise;
Sg: consistency of status with generative surprise; Sr: consistency of status with receptive surprise.

They also analyzed, mutual back and forth interactions,they noticed here that the principles of balance are more pronounced than they are in the larger portions of the networks where signed linking (and hence evaluation of others) takes place asymmetrically. They noticed that balance-based effects seem to be at work in the portions of the networks where directed edges point in both directions, reinforcing mutual relationships.

They also noticed that positive ties are more likely to be clumped together,while negative ties tend to act more like bridges between islands of positive ties.

Another interesting observation that they made, was that in their real data, an edge that was more embedded tended to be increasingly positive. These findings are consistent with the social-capital theory that states that embedded edges are more “on display" and thus tend to be positive.
The following picture shows these findings. Rnd denotes random signs created from the network, and real denotes the true signs that this network holds.


This paper presents a new perspective on how to reason social media sites by interpreting it as interactions between positive and negative relationships.
They also provide good insight with valid results, on to what theory depending on the network, is more fitted on explaining the nature of the network, i.e whether the network is directed or undirected.
I only have one doubt about the paper: They said that "...balance-based effects seems to be at work in the portions of the networks where directed edges point in both directions, reinforcing mutual relationship..", we could take these portions of the network as the community. Other papers, have only been interested in studying the community aspect of social networks, and feel that when in large scale these communities blend into the entire network, true human behavior is lost. Therefore we could question, if their status theory is modeling human behavior accurately.

None the less very interesting article, would highly recommend :)