,
Potential Theory for Directed Networks
PLoS ONE, 8 (2): e55437+ (11.02.2013)
DOI: 10.1371/journal.pone.0055437
Аннотация
Uncovering mechanisms underlying the network formation is a long-standing
challenge for data mining and network analysis. In particular, the microscopic
organizing principles of directed networks are less understood than those of
undirected networks. This article proposes a hypothesis named potential theory,
which assumes that every directed link corresponds to a decrease of a unit
potential and subgraphs with definable potential values on all nodes are
preferred. Combining the potential theory with the clustering and homophily
mechanisms, we deduce that the Bi-fan consisting of 4 nodes and 4 directed
links is the most favoured local structure in directed networks. Our hypothesis
get positive supports from extensive experiments on 15 directed networks drawn
from disparate fields, as indicated by the most accurate and robust performance
of Bi-fan predictor within the link prediction framework. In summary, our main
contributions are twofold: (i) We propose a new mechanism for the organization
of directed networks; (ii) We design the corresponding link prediction
algorithm, which can not only testify our hypothesis, but also find direct
applications in missing link prediction and friendship recommendation.
