martes, 22 de noviembre de 2016

Link Prediction Tool 1.0

One of the main novelties of the internet have been social networks so it is necessary to know their evolution over time. That is the main objective of the tool developed. 
The link prediction extension is based on Gephi uses all its advantages. Gephi is the open source leading visualization and exploration software for all kinds of graphs and networks.
In summary, an extension of Link Prediction was developed within a tool for managing graphs, representing social networks. 


Activity flow



This is an image of the steps that the user must follow to arrive at the results of the link prediction technique. First of all, it is necessary to obtain the graph file of the social network to analyze. For this, there are different tools or APIs to meet the objective. In addition, you can manually design the network to be analyzed or only part of it using the graph manager.
Then the type of graph loaded must be recognized, so Gephi does that job for us.



Type of graphs


To carry out the technique of Link Prediction is necessary to classify the type of graph according to different factors.

  • Time stamps on edges
    • Dynamic graph
    • Static graph
  • Edge type
    • Directed graph
    • Undirected graph
    • Mixed graph
  • For additional information
    • Nodes with addittional attributes
    • Nodes without additional attributes
According to the type of graph loaded there are variations for the algorithm of Link Prediction.


Choice of metrics


The catalog of metrics developed was added within the statistics panel. There are more than 15 different metrics to select, and all calculate the similarity between two users differently.

metricas.png


In addition, it is possible to cancel the task at runtime and also access old results easily. Depending on the chosen metric, the corresponding parameters must be configured in the application. For example, a capture of the configuration screen is included



In dynamic graphs, the user must define the initial time, called T0, to take that moment as the basis, and then compare the links that were generated dynamically with respect to the predictions. On the other hand, in static graphs, it is necessary to simulate the previous behavior. The technique hides random links from the graph, makes predictions, and then compares them to hidden links.

Range of nodes → It defines the users or nodes to consider within the technique

Number of predictions → Number of future relationships to be predicted by each user


Generation and evaluation of predictions


The three fundamental steps to carry out the link prediction technique for each user are:

1- Links are predicted according to the configured parameters.
2- Those who have the greatest similarity as predictions.
3- It is verified that the predictions performed correspond to the hidden links.

Visualization of results 


reporte final.png

  • Precision: # Correct Predictions / # Predictions
  • Recall: # Correct Predictions / # Hidden Links
  • Roc Curve: Compares correct predictions with respect to incorrect predictions as values ​​of similarity vary 
    • Area under the curve (AUC)
Ability to export or print results.

Additional Functions


Clustering

  • Calculate similarity for each edge of the initial graph 
  • Sort decreasing similarity ranking 
  • Removes percentage of irrelevant links

Metrics on a graph 

  • Do not calculate predictions 
  • Add column for selected metric in edge table 
  • Assigns similarity between each pair of existing users 
  • Possibility to export statistics within data table

Metric combination
  • It tries to improve the performance of individual predictor 
  • Combine those metrics with the same output type 
  • Maintains flexibility in parameter settings 
  • Similarity = Average of individual similarities

Contributions

The tool allows the prediction of links through a nice and simple interface with a Wide catalog of metrics. In addition, the combination and pre-processing (clustering) manage to improve the quality of the predictions.



Download Link Prediction Tool

4 comentarios:

  1. How can I install this tool on Gephi ?

    ResponderEliminar
    Respuestas
    1. You should run executable under gephi-master\modules\application\target\gephi\bin\

      Eliminar
  2. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  3. Este comentario ha sido eliminado por un administrador del blog.

    ResponderEliminar