Use of Rapid Probabilistic Argumentation for Ranking on Large Complex Networks

Abstract-- We introduce a family of novel ranking algorithms called ERank which run in linear/near linear time and build on explicitly modeling a network as uncertain evidence. The model uses Probabilistic Argumentation Systems (PAS) which are a combination of probability theory and propositional logic, and also a special case of Dempster-Shafer Theory of Evidence. ERank rapidly generates approximate results for the NPcomplete problem involved enabling the use of the technique in large networks. We use a previously introduced PAS model for citation networks generalizing it for all networks. We propose a statistical test to be used for comparing the performances of different ranking algorithms based on a clustering validity test. Our experimentation using this test on a real-world network shows ERank to have the best performance in comparison to well-known algorithms including PageRank, closeness, and betweenness. Ranking nodes in complex networks is an important challenge. Depending on the type of network and the application the meaning of a rank can be different. For the World Wide Web one is usually after popular and informative pages (e.g. For a citation network it is influential papers, for social networks (e.g. Facebook, LinkedIn) it is central/important persons. More recently, networks are tools for calculating trust and transitional trust [1]. Algorithms applied today to large networks often rely on an intuitive idea (e.g.