Probabilistic argumentation systems entity-transitive relation-implication model and document ranking as an efficient application

Abstract

This work is an endeavor towards analyzing complex networks. Mainly, a linkanalysis ranking (LAR) algorithm will be introduced, and related background will bedeveloped. Firstly, we introduce a graph based model we name Entity-Transitive Relation-Implication Model (ETRI) for analyzing complex networks. The underlying mathematicalmodel is built on Probabilistic Argumentation Systems (PAS), which are a combination ofthe use of propositional logic and probability theory. The ETRI model is a generic framework, capable of dealing with entities (e.g. web pages) in a network linked by atransitive relation (e.g. hypertext links). We apply ETRI modeling to the LAR problem.This is desirable because it builds on established evidential reasoning techniques usingclear semantics, however a direct application involves an NP-hard problem. Thus we present a family of novel algorithms we call ETRI Support Propagation forapproximations. We examine a member of these and show that it produces approximateresults in finite iterations. Its iterations are linear in the number of edges of the networklike PageRank. We run our algorithms on a snapshot of the CiteSeer citation network. We present a comparative study of different ranking schemes. Our studies reveal the transitionof dominance from local to global influences as an important characteristic of LARalgorithms. Our algorithms give results which can be highly correlated with citation countor PageRank when parameterized correspondingly.