This web site is no longer maintained and the content may be outdated.
Please visit www.cmpe.boun.edu.tr for up-to-date information.
 
CmpE RSS
No upcoming events...

Home / Graduate / M.S. Theses Completed
 
 
 
 
  Burak Çetin, 2005    

Thesis Title

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.
 
 
Boğaziçi University Department of Computer Engineering
Address: 34342 Bebek, Istanbul, TURKEY
Phone: +90 212 359 4523-24 Fax: +90 212 287 2461
general information: infocmpe.boun.edu.tr   webmaster: webmastercmpe.boun.edu.tr