An Analysis of Named Entity Disambiguation in Social Networks

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.