Weighted Graph: Make SNA More Accurate

In the latest three lectures, we are in touched with Social Network Analysis (SNA), which is a key component of the Social Network Research Field. And we get a superficial understanding of the different algorithm defined in SNA by doing some exercise on and after classes. And a question came to my mind afterwards. Did the social graph correctly represent the relations between human beings in SNS?

Let’s have an exercise to find the problem.

We assume that 5 people (From n1 to n5) are in the same SNS and their relationship can be represented by the graph below (Graph1).

Graph1: Normal Graph

Then we will use some algorithms in SNA to analysis it.

Degree Centrality: Cd(ni) C’d(ni) n1 4 1 n2 1 1/4 n3 3 3/4 n4 2 1/2 n5 2 1/2 Cd = 0.667	Closeness Centrality: Cc(ni) C’c(ni) n1 1/4 1 n2 1/7 4/7 n3 1/5 4/5 n4 1/6 2/3 n5 1/6 2/3 Cc = 0.26
Betweenness Centrality: Cb(ni) C’b(ni) n1 7/2 7/12 n2 0 0 n3 1/2 1/12 n4 0 0 n5 0 0 Cb = 0.5625

From the results of SNA, we can get some information:

1. The SNS shown by Graph1 is with high Degree Centrality and Betweenness Centrality.

2. Node n1 is the most important node in this SNS (with highest Cd, Cc and Cd).

However usually the relationships in the real SNS are not such simple, there are thousands types of relationships, for example, Tim and Bill are best friends while Tom and Sissy were just got to know, and obviously the strength of two previous relationships are not the same so I think it is unfair to assign all relations in SNS with the same value 1.

Let’s use the case showed by Graph1 again and adding some additional information: (1) n3 and n4 are best friends. (3) n3 and n5 are old friends. (4) n1 is a friend of n2 (5) n1 was just got to know n3, n4 and n5.

And this time we divide the relations into 4 levels and use a weighted graph to represent their relations again, as shown in Graph2.

Graph2: Weighted Graph

Now do the SNA again with the same algorithms.

Degree Centrality: Cd(ni) C’d(ni) n1 5/4 5/16 n2 1/2 1/8 n3 2 1/2 n4 5/4 5/16 n5 1 1/4 Cd = 0.333	Closeness Centrality: Cc(ni) C’c(ni) n1 1/14 2/7 n2 1/20 1/5 n3 3/37 12/37 n4 3/40 3/10 n5 3/41 12/41 Cc = 0.256
Betweenness Centrality: Cb(ni) C’b(ni) n1 Unfinished Unfinished n2 Unfinished Unfinished n3 Unfinished Unfinished n4 Unfinished Unfinished n5 Unfinished Unfinished Cb = Unfinished

Due to time limited, I cannot finish the calculation of Betweenness Centrality (Awful complex, I’m afraid (- -#)) and there may be some mistakes in calculation, but the result changes a lot:

1. Degree Centrality of the SNS getting lower, it is about 1/2 of the previous SNA.

2. Node n3 becomes the most important node (with highest Cd and Cc), while in the previous SNA it is n1.

In conclusion, the result completely changed when we take the weight of the relationships into consideration, and I believe using weighted graphs is a more reasonable and humane way to do SNA (If you do not consider the weight of relations to analysis the second case, the result will be unconvincing).

References:

• Angela Bohn & Norbert Walchhofer & Patrick Mair &Kurt Hornik: Social Network Analysis of Weighted Telecommunications Graphs
• M. E. J. Newman: Analysis of weighted networks
• http://toreopsahl.com/tnet/weighted-networks/node-centrality/

Epistemic Aim:Individual vs.Social

PART 1 --- An experiment: Individual vs. Social

We did an experiment in the last class, which is about the different of individual cognition and social cognition.

First we read a part of paper about Social Cloud, and then gave comments and thought about questions individually. Here are my individual answers (this is class activity one):

1. What is the definition of Social Cloud?

A Social Cloud is a resource and service sharing framework utilizing relationships established between members of a social network. – Answer from the paper (Unchanged after searching the Internet)

2. What are the possible applications of a Social Cloud?

Social Computation Cloud, Social Storage Cloud, Social Collaborative Cloud, Social Cloud for Public Science, Enterprise Social Cloud. –Answer from the paper

Friend Networks, Identification, Data Formats – Answer from the Internet

After that, we assembled our ideas and had a discussion on the same questions together by using a Google-doc, and finally we got the answers of the same questions, I also changed my answers and listed them (this is class activity two):

1. What is the definition of Social Cloud?

A Social Cloud is a scalable computing environment in which virtualized resources contributed by users are dynamically provisioned amongst a group of friends or colleagues. – Collect from group members

2. What are the possible applications of a Social Cloud?

Social Computation Cloud, Social Storage Cloud, Social Collaborative Cloud, Social Cloud for Public Science, Enterprise Social Cloud. – Keep unchanged.

PART 2 --- Behind the experiment: A change of epistemic aim

Actually, we only changed a little about the two answers after discussion, but even a little change makes a big difference, and the difference is included in our Group doc, instead of listing our answers and voting for the best one, we gave comments to other member’s answers or gave comments to comments, searched for references and evidences and absorbed ideas from others, even one of the group members listed the definition and applications of Cloud Computing (P.S. This concept a little-bit overlaps the concept of social cloud). It seems that our epistemic aim was changing trough the discussion. Take myself as an example, in activity one, I was concentrated on the paper in order to understand the concept, so in this part, my main epistemic aim was to answer the two questions, so my answers mainly based on the paper, in other word, I used functions of cognition and metacognition at that time and never in touch with the Epistemic Cognition level. But when editing the Google doc (Activity two), I seldom considered the content of the paper but focus on the other’s answers and comments to improve my knowledge of Social Cloud by gong through the references giving by others and writing down my own opinions, this is something about higher levels of cognition. And my epistemic aim totally changed.

PART 3 --- Conclusion

Using social ways to do idea generation and knowledge management is more effective. And it is more likely to ‘Think out of box’ by discussion in a social network environment because our epistemic aim changed a lot.

An Improvement in Video-sharing

In the 3^rd and 4^th week, we mainly focus on Psychology and Cognition in Online Social Network and a lot of concepts and real-life examples are raised in the lecture, I am aroused by the Hierarchy of Cognition.

Let’s go through the concept first. In the year of 1983, Kitchener, K.S. divided the cognition into three levels:

Level 1: Cognition: individuals memorize, read, write, and perceive media

Level 2: Metacognition: individuals monitor their own progress when they are engaged in these first-order tasks

Level 3: Epistemic Cognition: individuals reflect on the limits of knowing, the certainty of knowing, and criteria of knowing.

So what will happen when we take these concepts into social network? In my opinion, we can consider the level 1 as data, level 2 as information and level 3 as knowledge. Today’s social media provider mainly engaged in the functions of the 2^nd level maybe because the 1^st level is too easy and the 3^rd is too abstract to implement.

Actually I find a very good way to facilitate user experience at a metacognition level: allowing user to send real-time comments which will appear directly on a video so you can watch a video and check the comments or opinion made by others at the same time. As I know, there are three social website (Acfun , Bilibili and Tudou) have already implemented this kind of function (imitate from the Japanese website Niconico).

Video-sharing become much more interactive with everyone watching the same video discussing together, sharing their own understanding, knowledge and fun, these are all about the level of metacognition. It sounds perfect but just like the other social-network features, interaction dose not always bring good things. Sometimes meaningless messages may cover the whole screen making the viewer seriously interfered. And it seems to be more frequency that people split up into two groups and attack each other in the video with such features.

So, what’s your opinion? Do you think other video-sharing website would improve its user-experience in this way, why or why not?

References:

Nico Nico Douga –Wikipedia: http://en.wikipedia.org/wiki/Nico_Nico_Douga

视频弹幕网站- Wikipedia:

http://zh.wikipedia.org/wiki/%E8%A7%86%E9%A2%91%E5%BC%B9%E5%B9%95%E7%BD%91%E7%AB%99

Recommendation systems in social media

Welcome to my blog, this is my first post about the course Social Networking; I will not cover all the concepts of the 1^st and 2^nd classes but focus on the recommendation system of social media.

In general, there are two types of recommendation systems: Direct Social Recommendations and Derived Social Recommendations. 

The former one is easy to understand, the system will ask users to recommend the things they bought or watched to others they know. For instance, when you bought goods from Taobao.com, the system will ask you to recommend the goods to your friends or share it on social media. Actually, these systems are almost everywhere on the internet. 

While the latter is much more complicate. Distinct from the Direct Social Recommendations, the Derived Social Recommendations always have well-designed algorisms to predict the users’ favors. Take Youku as an example, whenever you finish watching a video, the system will find a list of recommended video to you. 

And the prediction algorisms are divided into two ways: Collaborative filtering and Content-based filtering. I will focus on the Collaborative filtering because it is more widely-used.

       The definition of Collaborative filtering from Wikipedia is: Collaborative filtering methods are based on collecting and analyzing a large amount of information on users’ behaviors, activities or preferences and predicting what users will like based on their similarity to other users. These filtering methods also have two types, one is User-based filtering, and another is Item-based filtering. In my opinion, the major difference between the two methods is, the User-based filtering take users into different groups while the Item-based filtering group the items. Let’s take a simple example to make it easier to understand.

We assume that Item1 and Item3 are correlated and User A and B have similar tastes, in the example upon, both the two users like Item1 and user A also like Item2, so in the User –based algorithm, Item2 is recommended to User B because the two users are in the same “group”. But when it turns to Item –based algorithm, the system recommends Item3 instead of Item2 to the two users for the reason that Item1 and item3 are in the same “group”.

I think it is really hard to give an absolute result about which one is better because the User –based algorithm seems more progressive while the Item –based one is more conservative and they give different ways of user experience. Maybe in most cases, Item –based algorithm is more accurate.

Welcome to comment on my blog.

References:

http://en.wikipedia.org/wiki/Recommender_system

http://en.wikipedia.org/wiki/Collaborative_filtering