Learn how to use Link Prediction Plugin for Gephi
By Dr. Verónica Espinoza, 2022.
Twitter @Verukita1
LinkedIn: Dra. Verónica Espinoza
Link-prediction plugin for Gephi, which allows to predict the next edges to be formed using different prediction algorithms. The implemented algorithms, only undirected, unweighted graphs are supported currently.
INTRODUCCTION
Social networks are a popular way to model interactions among people in a group or community. They can be visualized as graphs, where a vertex corresponds to a person in some group and an edge represents some form of association between the corresponding persons. Social networks are also very dynamic, because new edges and vertices are added to the graph over time. Understanding the dynamics that drive the evolution of a social network is a complex problem due to a large number of variable parameters [1].
The link prediction is an important research field in data mining. It has a wide range of scenarios. Many data mining tasks involve the relationship between the objects. Link prediction can be used for recommendation systems, social networks, information retrieval, and many other fields [2].
However, a comparatively easier problem is to understand the association between two specific nodes. For instance, some of the interesting questions that can be posed are: How does the association pattern change over time? What are the factors that drive the associations? How is the association between two nodes affected by other nodes? The problem that we want to tackle here is to predict the likelihood of a future association between two nodes, knowing that there is no association between the nodes in the current state of the graph. This problem is commonly known as the link prediction problem [3].
Link prediction methods
Brief description of eight commonly used prediction methods that use topology information about networks in the prediction process [1,3–5].
Table 1. Eight commonly used prediction methods.
(Elaborated by the author).
LINK PREDICTION PLUGIN FOR GEPHI
Link-prediction plugin for Gephi, which allows to predict the next edges to be formed using different prediction algorithms. Edges that are added to the network based on the prediction are marked accordingly. Users can limit the number of edges predicted. The plugin contains an evaluation component, which allows to compare the quality of the different algorithms regarding the graph on hand [6].
Features
In release 1.3.0 the plugin contains the following functionality:
Statistics: New edges can be added to an undirected graph using selected algorithms in the statistics tab. The number of new edges can be specified. In doing so, n new edges are added to the graph iteratively. The calculation of the next predicted edge is always based on the graph of the preceding iteration step.
Filter: The added edges can be displayed by means of filters. On the one hand, the corresponding algorithm is specified as the filter criterion. On the other hand, the number of added edges can also be restricted.
Evaluation: Based on an initial graph and a validation graph the accuracy of the link predictions using different algorithms are evaluated. Besides the final accuracy, the generated report also shows the accuracy after each iteration step.
Limitations
With the limitations of the implemented algorithms, only undirected, unweighted graphs are supported currently.
The plugin was tested using graphs with less than a thousand nodes. Link predictions in larger networks can lead to long runtimes.
Algorithms for link prediction implemented in Gephi
Link prediction is based on an existing network and attempts to predict new edges. The most popular application is the suggestion of new friends on social networking platforms. To predict a new edge, different algorithms exist. The plugin allows to easily add new algorithms. Currently, the algorithms common neighbours and preferential attachment are implemented. To show the functionality of the algorithms, the following example graph is used [6].
1.-Common neighbours
Common neighbours calculates for two unconnected nodes how many common neighbours exist. The higher the calculated value, the more likely a new edge will be added between the two nodes.
The following formula represents, how the number of common neighbours of two nodes X and Y can be calculated. The call to the function N(::) returns all neighbours of a node in a set, e.g. N(A) returns all neighbour nodes of node A.
Applied to the above example graph, the common neighbour algorithm would predict a new edge between nodes A and C. The following examples show some of the calculated values:
2.-Preferential attachment
The basic assumption with Preferential Attachment is that the probability that a node is affected by a newly added edge, is just proportional to the number of neighbours. The more neighbours a node has, the larger the likelihood that it will be affected.
To calculate preferential attachment, the number of neighbours of both nodes are multiplied by each other. The call to the function N(::) returns again all neighbours of a node in a set, e.g. N(A) returns all neighbours of node A.
Applied to the above example graph, preferential attachment would predict an edge between node A and G and calculate the following values:
The code is visible on Github.
STEPS TO PREDICT NEW LINKS IN GEPHI
Download the plugin here.
Step 1: Run Link-prediction option in the Statistics panel of Gephi.
Step 2: Select link prediction algorithm and set the iterations.
Step 3: Evaluate prediction algorithms.
Step 4: Review the results of the predictions in the data lab.
Step 5: Filter the predictions according to the algorithm you want. The number of added edges can also be restricted.
Finally, review the results of the predictions for each algorithm.
👍Thanks for reading!
😃This is my Twitter
RESOURCES
Do you want to learn more about Gephi?
I share a list of stories that I have written on medium where you will find interesting information and resources.
- What is Gephi? Meet this useful network analysis tool
- How to publish your Gephi network to the web.
- Link Prediction Plugin for Gephi.
- Position Ranking Plugin for Gephi,
- How to visualize a Spotify Network in Gephi in just a few steps!
- How to use Network Splitter 3D plugin for Gephi
- Groups by Partition Plugin for Gephi: “Each node is the aggregation of a group of nodes”
REFERENCES
1. Social Networks: Modelling and Analysis [Internet]. Routledge & CRC Press. [cited Nov 4, 2022]. Available in: https://www.routledge.com/Social-Networks-Modelling-and-Analysis/Aggrawal-Anand/p/book/9780367541392
2. Dong L, Li Y, Yin H, Le H, Rui M. The Algorithm of Link Prediction on Social Network. Mathematical Problems in Engineering.
September 17, 2013;2013:e125123.
3. Link Prediction Algorithms [Internet]. [cited Nov 4, 2022]. Available in: http://be.amazd.com/link-prediction/
4. Laishram R. Link Prediction in Dynamic Weighted and Directed Social Network using Supervised Learning. Dissertations — ALL [Internet]. January 1, 2015; Available in: https://surface.syr.edu/etd/355
5. Zhang M, Chen Y. Link Prediction Based on Graph Neural Networks [Internet]. arXiv; 2018 [cited Nov 4, 2022]. Available in: http://arxiv.org/abs/1802.09691
6. Link-prediction plugin for Gephi [Internet]. [cited Nov 4, 2022]. Available in: https://gephi.org/plugins/#/plugin/link-prediction
