Graph theory provides a way of using graphs to represent networks, and is often used in the development and study of online social networks.
Image source: freepik
At the core of graph theory is understanding the nature of connections, their relationship to one another, and calculating the importance of each node. ‘Importance’ is calculated, in different ways, from the connections between individuals (or nodes) in the network. In this post I will outline how graph theory supports Neighbourhood’s marketing strategy.
The origins of Graph theory: connections across a city
The origin of Graph theory: Leonard Euler’s Solution to the Königsberg Bridge Problem
“Graph theory was born in 1736 with Euler’s solution [to] the Königsberg bridge problem, which asked whether it was possible to plan a walk over the seven bridges of the town without re-tracing one’s steps. Euler realised that the problem could be rephrased in terms of a graph whose vertices corresponded to the four regions of the city, and whose edges corresponded to the seven bridges each joining a pair of the regions.”
Graph theory terminology
Image source: Math insight
First of all, a quick explanation of graph theory terminology:
- Nodes: (also known as vertices) A node is a point on the network, for example in a social network, a node is a person
- Edges: An edge is a connection (or link) between two nodes. May be directed (only go in one direction) or undirected
Edge betweenness
The edge betweenness of nodes in a network is calculated from how much traffic flows through its connecting edges. This establishes the level of connectivity between each node (or user), and all other nodes.
The Girvan-Newman method or algorithm is often used to calculate this. To help visualize the concept, this graph shows the nodes with the highest calculated betweenness centrality in blue:
Image source: Claudio Rocchini
Edge betweenness for target marketing
Neighbourhood is about connecting people to local opportunities to pursue their interests, which in turn connects them to other people in their neighbourhood. Neighbourhood users which have high ‘betweenness’ will be most likely to help with:
- Increasing the number of activities and groups on Neighbourhood
- Spreading the word and increasing our user base with ‘high value’ new users
This is based upon the insight that trust builds up quickly between individuals that share interests. Meaning the most connected, trusted users will invite the most valuable new users: those who are deeply engaged in mutual interests, and that enter the platform with a high level of trust in at least one existing user. These ‘high value’ new users will be most likely to play a key role in enriching subhood interest groups on Neigbhourhood.
Image source: Universidad Icesi
An important pillar of our marketing strategy is friend-get-friend incentives, which encourage our users to invite others. For this we will identify Neighbourhood users who have high Betweenness Centrality, and target them with personalized, extra incentives to start new activities and groups on Neighbourhood, and to invite new users.