A graph or network is a way of representing relationships among a collection of items[1]. A graph consists of nodes and edges, where the nodes are the items and the edges are the links between them. The number of nodes to which a node is connected is known as the degree of the node. When nodes with similar attributes are grouped together this is known as Clustering.

In Skillted, a user (with a skill) is represented by a node while an edge represents relationship between two users intending to barter skills. Clusters would be formed around users with desirable rare skills as other users would interact to trade skills. Also, the local clustering coefficient of a user(node) in the network, determined by the probability that two randomly selected affiliates of a user are affiliates with each other, can be used to ascertain how related users are in the network.

In graph theory, centrality measures identify the most important nodes in a graph.

Degree centrality

Definition: This refers to the number of nodes to which a node is connected.
Application: A high degree of a node in this graph could mean the user has a rare skill and has many other users that are willing to trade skills. Hence the degree centrality for a user with a rare skill would be high compared to users with a common skill.

Closeness centrality

Definition: This is used to determine how close a node is to other nodes in the network.
Application: The closeness of a user to other Skillted users also depends on how many skills he has to trade. The more skills he has to trade, the more users he would get to interact with and the more edges would link the user in the graph to other users. The closeness centrality of the user is thus measured by the inverse of the distance from the user’s node to all the other Skillted users’ node in the graph, where the distance between each node is the shortest path between them. Hence a user with multiple skills would be closer to the other nodes in this network.

Betweenness centrality

Definition: This helps determine the number of times a node acts as a bridge along the shortest path between two other nodes. It gives a measure for the number of users separating the user from another user with a desired skill.
Application: For users with skills that do not match, the betweenness centrality defines the shortest path between them if any exists.

The centrality measures can used to understand relationships and trends within the Skillted network which would help inform better business decisions. For example if there is a high in-degree centrality to a user that has a skill, say, Piano tutor, a need could be seen for these kinds of tutors and adverts placed for people willing to pay for the service rather than barter a skill.

 

Update: Read follow up post, Final thoughts on Graph Theory for Skillted here

 

References

1. Networks, Crowds, and Markets: Reasoning About a Highly Connected World By David Easley and Jon Kleinberg – http://www.cs.cornell.edu/home/kleinber/networks-book/

2. Lecture Notes on Graph Theory – http://www.edshare.soton.ac.uk/8816/