To access the full text documents, please follow this link: http://hdl.handle.net/2117/26091

Link prediction in very large directed graphs: Exploiting hierarchical properties in parallel
Garcia Gasulla, Dario; Cortés García, Claudio Ulises
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. KEMLG - Grup d´Enginyeria del Coneixement i Aprenentatge Automàtic
Link prediction is a link mining task that tries to find new edges within a given graph. Among the targets of link prediction there is large directed graphs, which are frequent structures nowadays. The typical sparsity of large graphs demands of high precision predictions in order to obtain usable results. However, the size of those graphs only permits the execution of scalable algorithms. As a trade-off between those two problems we recently proposed a link prediction algorithm for directed graphs that exploits hierarchical properties. The algorithm can be classified as a local score, which entails scalability. Unlike the rest of local scores, our proposal assumes the existence of an underlying model for the data which allows it to produce predictions with a higher precision. We test the validity of its hierarchical assumptions on two clearly hierarchical data sets, one of them based on RDF. Then we test it on a non-hierarchical data set based on Wikipedia to demonstrate its broad applicability. Given the computational complexity of link prediction in very large graphs we also introduce some general recommendations useful to make of link prediction an efficiently parallelized problem.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Computational complexity
Data mining
Algorithms
Economic and social effects
Forecasting
Graphic methods
Semantic Web
Statistical tests
Complexitat computacional
Mineria de dades
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
CEUR-WS.org
         

Show full item record

Related documents

Other documents of the same author

Garcia Gasulla, Dario; Poch, M; Nieves Sánchez, Juan Carlos; Cortés García, Claudio Ulises
Garcia Gasulla, Dario; Cortés García, Claudio Ulises; Nieves Sánchez, Juan Carlos
Gómez Sebastià, Ignasi; Garcia Gasulla, Dario; Barrué Subirana, Cristian; Vázquez Salceda, Javier; Cortés García, Claudio Ulises
Garcia Gasulla, Dario; Cortés García, Claudio Ulises
Moreno Vázquez, Jonatan; Garcia Gasulla, Dario; Cortés García, Claudio Ulises
 

Coordination

 

Supporters