What model enable to understand better a graph entities interactions through link prediction

This repository contains source code to research concerning linkprediction

Installation

To use the code in this repo, first you'll need to install Python requirements using the following command

pip install -r requirements.txt

Then, install our custom version of EvalNE using pip

pip install git+https://github.com/thunlp/OpenNE.git
pip install git+https://github.com/Jacobe2169/EvalNE

Finally, install the Python library graph-tool.

First experience: Does a graph model still is the best to predict itself ?

First hand, it's important to indicate why we want to do this ! For a better understanding of a network, we need to know what model structured it. One way of doing that is through link prediction. Our hypothesis is that if a specific model is able to catch how most of vertices are linked then the graph is structured by it. One way to verify this hypothesis is to evaluate a model in a link prediction task.

In this experiment, we evaluate different link prediction methods from heuristics to deep learning methods. For that we use a custom version of EvalNE for evaluating link prediction methods. We developed a serie of functions for generating graph based on the following models:

• Spatial model
• Stochastic Block Model
• Configuration Model
• Random (ER)

Generate a graph using the library

All graph generator can be found in the module lib.random. For every graph generator, you can set the number of edges and nodes in the resulting graph.

For example, if you want to generate a graph following the stochastic block model, use the follwing code :

from lib.random import stochastic_block_model_graph
G = stochastic_block_model_graph(nb_nodes=300,nb_edges=1200,nb_com=5,percentage_edge_betw=0.01)

If you wish to generate a dataset containing generated graph with different configurations, you can use the script generate_random_graph.py using the following command :

python generate_theoric_random_graph.py <output_dir>

You can modify the parameters of each configuration for each model in the script source code.

Evaluation

To run the evaluation of link prediction method on a dataset, use the run_eval.py script:

python run_eval.py <graph_datasset_dir> <output_dir> [-f <graph_file_format(gexf, gml or txt)> ][-t <train_frac>] [-v verbose] 

Second, What about mixed model graphs ?

Generate graph using a mixture of model

from lib.random import mixed_model_spat_sbm
G = mixed_model_spat_sbm(nb_nodes=300,nb_edges=1600,nb_com=3,alpha=0.3) 
#Here alpha is to quantify fraction of the edges selected using the SBM model

Evaluate our link prediction method on mixed model

(TODO Explain the erosion model)

python eval_mixed_model.py <graph_datasset_dir> <output_dir> [-f <graph_file_format(gexf, gml or txt)> ][-t <train_frac>] [-v verbose]

Authors

Jacques Fize, Rémy Cazabet