Emerging applications of link analysis for ranking [Elektronische Ressource] / von Paul-Alexandru Chirita

Paul-Alexandru Chirita

Sujets

• Informatik

Informations

• Publié par: gottfried_wilhelm_leibniz_universitat_hannover
• Publié le: 01 janvier 2007
• Nombre de lectures: 34
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Emerging Applications
of Link Analysis for Ranking
Von der Fakultat¨ fur¨ Elektrotechnik und Informatik
der Gottfried Wilhelm Leibniz Universit¨at Hannover
zur Erlangung des Grades eines
Doktor-Ingenieurs
(abgekurzt:¨ Dr.-Ing.)
genehmigte Dissertation
Von Dipl.-Ing. Paul - Alexandru Chirita
geboren am 07.07.1980 in Bukarest, Rumanien.¨
2007Emerging Applications of Link Analysis for Ranking
Kommission:
Referent: Prof. Dr. Wolfgang Nejdl
Gottfried Wilhelm Leibniz Universit¨at Hannover,
Hannover, Deutschland
Korreferent: Prof. Dr. Ricardo Baeza - Yates
Universit¨at Pompeu - Fabra, Barcelona, Spanien
Korreferent: Prof. Dr. Klaus Jobmann
Gottfried Wilhelm Leibniz Universit¨at Hannover,
Hannover, Deutschland
Tag der Promotion: 24. Mai 2007
2Zusammenfassung
DerstarkeZuwachsvonelektronischverfugb¨ arenDatenhabenstarkzurPopularit¨atvonSuchmaschinenbeigetra-
gen. Allerdings sind die Nutzer von Suchmaschinen typischerweise nur an den wenigen Dokumenten interessiert,
dieimBezugaufihreArbeitdiehoc¨ hsteRelevanzbesitzen. EsistalsosehrwichtighochwertigeRankingmethoden
zu entwickeln, die effizient diese relevanten Dokumente fu¨r die verschiedenen Aktivit¨aten zur Informationssuche
identifizieren, die solche Nutzer entwickeln.
DieseArbeitenth¨altzweiBeitr¨agezudemBereich“InformationRetrieval”. ErstensidentifizierenwirdieAnwen-
dungsbereiche, indeneinnutzerorientiertesRankingderzeitnichtvorhandenist, obwohlesextremnotwendigist,
um einen hochqualitativen Zugang zu den fur¨ einen Nutzer relevanten Ressourcen zu erm¨oglichen. Zweitens en-
twickelnwirfu¨rjedenvondiesenAnwendungsbereichendieentsprechendenRankingalgorithmen, dieaufsozialen
Charakteristika aufbauen und diese ausnutzen, entweder auf einem makroskopischen oder einem mikroskopis-
chen Niveau. Dies wird durch “Link Analysis” Techniken erreicht, die auf der graphbasierten Darstellung der
Verknupfung¨ en zwischen Objekten bauen, um sie zu ordnen oder einfach um Muster im Bezug auf deren soziale
Eigenschaften zu erkennen.
Wir fangen an und argumentieren, dass das Ranken von Objekten auf dem Desktop sehr effektiv den Zugang zu
allen Ressourcen auf dem Desktop verbessern kann. Dafu¨r schlagen wir vor, die “Link Analysis” Methoden auch
auf dem Desktop zu nutzen unter Verwendung von Statistiken ber das Nutzerverhalten. Wir zeigen, dass ein auf
diese Weise entwickeltes Ranking sehr vorteilhaft fur¨ das Anwendungsszenario einer Desktop-Suchmaschine ist.
AnschlieendsetzenwirdieselbengrundlegendenIdeenfu¨rdieErkennungvon“SpamEmails”ein. Dazuverbinden
wir Menschen in sozialen Netzwerken, basierend auf dem Austausch von Emails zwischen diesen, und leiten
daraus eine Reputationsmetrik ab, die b¨oswillige Mitglieder jeder Community isoliert. Auf eine a¨hnliche Weise
modellieren wir mehrere kunst¨ liche Linkstrukturen auf einer h¨oheren Abstraktionsebene, die Link Analysis
Algorithmen im allgemeinen negativ beeinflussen k¨onnen. Wir geben auch an, wie man solche Linkstrukturen
im Anwendungsszenario “Ranken von Webseiten” entfernen kann.
Der letzte Teil dieser Arbeit nutzt manuell erstellte Informationsrepositorien, um die Web Suche zu personal-
isieren. Wir untersuchen zwei verschiedene Arten von solchen Repositorien, solche die global bearbeitet werden
k¨onnen und solche die individuell bearbeitet werden k¨onnen. Im ersten Fall wenden wir Link Analysis Tech-
¨niken auf o¨ffentliche Webverzeichnissen an, wie zum Beispiel das Open Directory, und definieren geeignete Ahn-
lichkeitsmetriken, die die Suchergebnisse nach den Pr¨aferenzen des Nutzers anordnen. Fur¨ individuell bearbeit-
bare Repositorien, schlagen wir eine Methode zur Erweiterung von Suchanfragen vor, die sowohl auf der Analyse
von Text, als auch auf Link Analysis Methoden in Zusammenhang mit “Personal Information Repositories”
beruhen. Ausfu¨hrliche Experimente, die beide Vorgehensweisen auswerten, zeigen in beiden Fallen wesentliche
Verbesserungen im Vergleich zu einer herko¨mmlichen Suche mit Google.
3Emerging Applications of Link Analysis for Ranking
Schlagw¨orter
Informationswiedergewinnung, Data Mining, Internet
4Abstract
The booming growth of digitally available information has thoroughly increased the popularity
of search engine technology over the past years. At the same time, upon interacting with this
overwhelming quantity of data, people usually inspect only the very few most relevant items for
their task. It is thus very important to utilize high quality ranking measures which efficiently
identify these items under the various information retrieval activities we pursue.
In this thesis we provide a twofold contribution to the Information Retrieval field. First, we
identify those application areas in which a user oriented ranking is missing, though extremely
necessary in order to facilitate a qualitative access to relevant resources. Second, for each
of these areas we propose appropriate ranking algorithms which exploit their underlying social
characteristics,eitheratthemacroscopic,oratthemicroscopiclevel. Weachievethisbyutilizing
link analysis techniques, which build on top of the graph based representation of relations
between resources in order to rank them or simply to identify social patterns relative to the
investigated data set.
We start by arguing that Ranking Desktop Items is very effective in improving resource access
withinPersonalInformationRepositories. Thus,weproposetomovelinkanalysismethodsdown
to the PC Desktop by exploiting usage analysis statistics, and show the resulted importance
ordering to be highly beneficial for the particular scenario of Desktop Search.
We then apply the same technique for Spam Detection. We connect people across email social
networks based on their email exchanges and induce a reputation metric which nicely isolates
malicious members of a community. Similarly, we model several higher level artificial constructs
which could negatively manipulate generic link analysis ranking algorithms, and indicate how
to remove them in the case of Web page ranking.
Finally, we exploit manually created large scale information repositories in order to Personalize
Web Search. We investigate two different types of such repositories, namely globally edited
ones and individually edited ones. For the former category we project link analysis onto public
taxonomies such as the Open Directory and define appropriate similarity measures which order
the search output in accordance to each user’s preferences. For the latter one, we propose to
expand Web queries by utilizing both text and link analysis on top of Personal Information
Repositories. Extensive experiments analyzing both approaches show them to yield significant
improvements over regular Google search.
5Emerging Applications of Link Analysis for Ranking
Keywords
Information Retrieval, Data Mining, World Wide Web
6Foreword
The algorithms presented in this thesis have been published within several Infor-
mation Systems conferences, as follows.
The usage analysis based Desktop ranking ideas were split across two interest
areas: (1)SemanticWeb,whenweaimedforspecificuseractions,modeledusually
using ontologies, [61, 62, 63], and (2) Information Retrieval, when all activities
were logged and analyzed from a statistical point of view [66]:
• Beagle++: Semantically Enhanced Searching and Ranking on the Desktop.
By Paul - Alexandru Chirita, Stefania Ghita, Wolfgang Nejdl, Raluca Paiu.
In Proceedings of the 3rd European Semantic Web Conference (ESWC),
Budva, Montenegro, 2006 [63].
• Activity-Based Metadata for Semantic Desktop Search. By Paul - Alexan-
dru Chirita, Stefania Ghita, Rita Gavriloaie, Wolfgang Nejdl, Raluca Paiu.
In Proceedings of the 2nd European Semantic Web Conference (ESWC),
Heraklion, Greece, 2005 [61].
• Semantically Enhanced Searching and Ranking on the Desktop. By Paul -
Alexandru Chirita, Stefania Ghita, Wolfgang Nejdl, Raluca Paiu. In Pro-
ceedings of the Semantic Desktop Workshop held at the 3rd International
Semantic Web Conference, Galway, Ireland, 2005 [62].
• Analyzing User Behavior to Rank Desktop Items. By Paul - Alexandru
Chirita, Wolfgang Nejdl. In Proceedings of the 13th International Sym-
posium on String Processing and Information Retrieval (SPIRE), Glasgow,
United Kingdom, 2006 [66].
The other two chapters have been focused exclusively on Information Retrieval
techniques. Theworkonspamdetectionwaspresentedinless,butmoreimportant
conferences, after major parts of the research had been already completed [58, 44,
28]:
7Emerging Applications of Link Analysis for Ranking
• MailRank: UsingRankingforSpamDetection. ByPaul-AlexandruChirita,
Jrg Diederich, Wolfgang Nejdl. In Proceedings of the 14th ACM Interna-
tional CIKM Conference on Information and Knowledge Management, Bre-
men, Germany, 2005 [58].
• Site Level Noise Removal for Search Engines. By Andre Carvalho, Paul
- Alexandru Chirita, Edleno Silva de Moura, Pavel Calado, Wolfgang Ne-
jdl. In Proceedings of the 15th International World Wide Web Conference
(WWW), Edinburgh, United Kingdom, 2006 [44].
• An Analysis of Factors used in Search Engine Ranking. By Albert Bifet,
Carlos Castillo, Paul - Alexandru Chirita, Ingmar Weber. In Proceedings
of the Adversarial Information Re