Graph Theory and Social Networks

Graph theory is a mathematics’s field which studies graphs. The graph itself is defined as a collection of nodes which are connected by edges. The edges can be directed or undirected. Social networks can also be represented as a graph; for example a user as a node and its friends which links to the user is considered as an edge. Since a graph, as an abstraction level, has so many functions, we can measure or analyse a social network using this concept.


Graph Centrality

There are four types of graph centrality [1]:
(i) Degree Centrality
A node which has more edges, has a higher degree than the fewer ones. For directed graph, there are in-degree, how many links points to this node, and out-degree, how many links out of this node. This concept can be a measure of how important the node is, especially for social network sites. Consider the user as a node and followers as the links to the node. The more followers a user has, the more important he is.

(ii) Betweenness Centrality
This centrality is related with communication flow. The node which has a higher centrality is more essential for communication. In a social network, two users have a high betweenness because they have high interaction between each other. Facebook for example, can then filters the user’s updates.

(iii) Closeness Centrality
Closeness centrality is the inverse of farness which is the sum of its distances to every other vertex in a graph. This centrality determines how quickly a message travels from a node to whole nodes in a graph. In a social network, it represents when a user wants to deliver a message to others.

(iv) Eigenvector Centrality
Eigenvector centrality calculates the connection of a node to the important node. For example, a user x is followed by Barrack Obama, then the user x is treated as more important than y who is not followed by Barrack Obama, even if y has more followers than x. The eigenvector centrality does not treat all nodes equally. The best example of this centrality is PageRank which is used by Google to rank all websites for its search engines.

Triadic Closure

If two people in a social network have a friend in common, then there is an increased likelihood that they will become friends themselves at some point in the future [1]

Imagine two users A and B are friends each other in a social network. B is friend of C and D. Then, there is a high possibility that A will be a friend of and D then they tend to be a completed graph, connect to each other. In other words, it is possible all users connect each other in a social network.

However, each connection can not be treated equally, there is a strong and weak ties between them. These kind of relationships are also popular in a real world, is not it?

If a node A has edges to nodes B and C, then the B-C edge
is especially likely to form if A’s edges to B and C are both
strong ties [1]

People also have a preferential attachment, they have a preference to attach to somebody, not to all people. They have an unbalanced relationship to all people. Therefore, it is unlikely that there would be a situation which all people in a social network connect to each other.


[1] Tiropanis, T. A Lecture Slide: Social Networking Technologies: Graph Theory and Social Networks. 2016.


Leave a Reply

Your email address will not be published. Required fields are marked *