Discriminative link prediction using local links, node features and community structure

De, Abir ; Ganguly, Niloy ; Chakrabarti, Soumen (2013) Discriminative link prediction using local links, node features and community structure In: 2013 IEEE 13th International Conference on Data Mining, Dec. 7, 2013 to Dec. 10, 2013, Dallas, TX, USA.

Full text not available from this repository.

Official URL: https://www.computer.org/csdl/proceedings/icdm/201...

Related URL: http://dx.doi.org/10.1109/ICDM.2013.68


A Link Prediction (LP) algorithm is given a graph, and has to rank, for each node, other nodes that are candidates for new linkage. LP is strongly motivated by social search and recommendation applications. LP techniques often focus on global properties (graph conductance, hitting or commute times, Katz score) or local properties (Adamic-Adar and many variations, or node feature vectors), but rarely combine these signals. Furthermore, neither of these extremes exploit link densities at the intermediate level of communities. In this paper we describe a discriminative LP algorithm that exploits two new signals. First, a co-clustering algorithm provides community level link density estimates, which are used to qualify observed links with a surprise value. Second, links in the immediate neighborhood of the link to be predicted are interpreted %at face value, but through a local model of node feature similarities. These signals are combined into a discriminative link predictor. We evaluate the new predictor using five diverse data sets that are standard in the literature. We report on significant accuracy boosts compared to standard LP methods (including Adamic-Adar and random walk). Apart from the new predictor, another contribution is a rigorous protocol for benchmarking and reporting LP algorithms, which reveals the regions of strengths and weaknesses of all the predictors studied here, and establishes the new proposal as the most robust.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Institute of Electrical and Electronic Engineers.
ID Code:99977
Deposited On:12 Feb 2018 12:26
Last Modified:12 Feb 2018 12:26

Repository Staff Only: item control page