JADERICK P. PABICO
Institute of Computer Science, University of the Philippines Los Baños, Laguna
jppabico@uplb.edu.ph
Date Received: June 25, 2014; Date Published: August 15, 2014
Asia Pacific Journal of Multidisciplinary Research
P-ISSN 2350-7756 | E-ISSN 2350-8442 | Volume 2, No. 4, August 2014
An Analysis of Named Entity Disambiguation in Social Networks 716 KB 1 downloads
JADERICK P. PABICO Institute of Computer Science, University of the Philippines Los...
The solution to the problem of disambiguating named entities in online social networks is introduced in this paper. The problem is solved via a two-step reduction process: A reduction to the Maximal Common Subgraph Problem (MaxSubgraph), and then a further reduction to the Maximal Clique Problem (MaxClique). An analysis of this process provides an upper bound of the runtime of the solution which was found to run in O(|V |k k2), where |V| is the maximum cardinality of vertices of the social networks and k is the size of the clique.
Keywords – name disambiguation, social networks, most common subgraph