Partitioning massive graphs for content oriented social network analysis [Elektronische Ressource] / vorgelegt von Maximilian Viermetz

Riks

Sujets

• Informatik

Informations

• Publié par: heinrich-heine-universitat_dusseldorf
• Publié le: 01 janvier 2008
• Nombre de lectures: 36
• Langue: Deutsch
• Poids de l'ouvrage: 4 Mo

Extrait

Partitioning Massive Graphs for
Content Oriented Social Network
Analysis
Inaugural-Dissertation
zur
Erlangung des Doktorgrades der
Mathematisch-Naturwissenschaftlichen Fakultat¨
der Heinrich-Heine-Universitat¨ Du¨sseldorf
vorgelegt von
Maximilian Viermetz
aus London, U.K.
09.07.2008Aus dem Institut fu¨r Informatik
der Heinrich-Heine Universit¨at Du¨sseldorf
Gedruckt mit der Genehmigung der
Mathematisch-Naturwissenschaftlichen Fakult¨at der
Heinrich-Heine-Universit¨at Du¨sseldorf
Referent: Prof. Dr. Stefan Conrad
Heinrich-Heine-Universit¨at Du¨ssel-
dorf, Germany
Koreferent: Prof. Dr. Dietmar Seipel
Julius-Maximilians-Universit¨at
Wu¨rzburg, Germany
Tag der mu¨ndlichen Pru¨fung: 12.06.2008To Felicitas. for all she has given.
To Caroline, for suffering my involvement.
To Kurt, for his unconditional support.
And since you know you cannot see yourself,
so well as by reflection, I, your glass,
will modestly discover to yourself,
that of yourself which you yet know not of.
— William Shakespeare
Julius Caesar
Act I Scene IIZusammenfassung
Heutzutage sind Firmen in einer immer enger vernetzten Welt einer stetig wachsenden
Informationsflut ausgesetzt. Berichte, Nachrichten und Konsumentenkommentare sind
jederzeit und ub¨ erall ub¨ er Plattformen wie Weblogs oder Newsgroups verfug¨ bar. Die
M¨oglichkeit der Kommunikation ub¨ er elektronische Medien wird immer st¨arker genutzt.
Diese gewinnen dadurch immer mehr Einfluss. Preisvergleiche zwischen verschiedenen
Anbietern, Testberichte von professionellen Agenturen sowie der Austausch von Be-
nutzern ub¨ er gemeinsame Erfahrungen und Beschwerden sind nur einige Bereiche in
denen moderne Kommikationsmedien eine immer st¨arkere Rolle spielen.
Eine Konsequenz der rasanten Entwicklung von modernen internetbasierten Kommu-
nikationsmedien ist die starke Entwicklung und Nutzung von asynchronen Kommunika-
tionsmodi, wie zum Beispiel Email oder Newsgroups, und synchronen Kommunikation-
smodi wie sie durch Instant Messaging angeboten werden. Durch ihre bequeme Hand-
habung, eine so gut wie kostenlose Nutzung und eine nahezu sofortige Kommunikation
haben sie die moderne Gesch¨aftswelt komplett durchdrungen.
Die Bereitstellung moderner Kommunikationsinfrastruktur auf elektronischer Basis
erm¨oglicht die Erfassung und Sammlung neuer Daten in ungeahntem Maße. Diese
Datenquellensinddasprim¨areZielmodernerTechnikenimBereichDataMiningundIn-
formationsextraktion. Daraus entstehende Kommunikationskorpora werden seit einiger
Zeit analysiert und unter dem Aspekt des Social Network Analysis eingehend betra-
chtet. Die Schwerpunkte dieser Betrachtung kann man in zwei Kategorien einteilen;
erstens die Untersuchung der Struktur von Kommunikationsgraphen und zweitens die
inhaltliche Analyse der Kommunikationen um vorher unbekannte aber jedoch interes-
sante Informationen zu extrahieren.
Social Network Analysis findet in der heutigen Informatik immer mehr Anklang.
Durch die Analyse von Kooperationsnetzwerken durch Publikationen (co-citation net-
works) wurde seit 1990 die Anwendung von Graphanalyse auf Netzwerke aller Art in
Augenschein genommen.
Die Entdeckung und das Herausarbeiten neuer und markanter Trends und Markten-
twicklungen k¨onnen das Aufkommen von einflussreichen Themen und Schwerpunkten in
PlanungundKommunikationvonUnternehmenbeeinflussen. VonbesonderemInteresse
ist vor allem die Beobachtung der Entwicklung solch relevanter Themen ub¨ er die Zeit.
Die Resultate von Social Network Analysis werden heutzutage in den unterschiedlich-
stenBereicheneingesetzt. SowerdenNetzwerkanalysenbeiderErkennungundBek¨amp-
fungvonterroristischenNetzwerkenbishinzurSNAbasiertenBewertungundSortierung
des Internets durch Google, der besten Gesch¨aftsidee des letzten Jahrhunderts, genutzt.
Zudem wurden im Fachgebiet der Informationsverarbeitung in den letzten Jahren große
iZUSAMMENFASSUNG
Fortschritte erzielt. Diese erm¨oglichen eine wesentlich pr¨azisere automatische Analyse
und Klassifikation von Texten.
Ansatz dieser Dissertation ist es grundlegende Aspekte aus Social Network Aanalysis
und Informationsbverarbeitung zu vereinen und Kommunikationskorpora unter struk-
turellensowieinhaltlichenBlickwinkelngleichzeitigzubetrachten. DieseArbeitkonzen-
triert sich auf die Herausarbeitung von Kommunikationsmustern, welche sich aus dem
Zusammenspiel von SNA und inhaltlicher Segmentierung durch den Austausch elektro-
nischer Information ergeben. Der Fokus liegt prim¨ar in der Analyse von textbasierten
Nachrichten,wirdaberdarub¨ erhinausweitereQuellenvongerichtetenund
Kommunikationsformen betrachten.
iiAbstract
For companies acting on a global scale, the necessity to monitor and analyze news
channels and consumer-generated media on the Web, such as web-logs and newsgroups,
is steadily increasing. In particular the identification of novel trends and upcoming
issues, as well as their dynamic evolution over time, is of utter importance to corporate
communications and market analysts.
Thedevelopmentofthecommunicationinfrastructureasprovidedbyelectronicmeans
and delivered via the Internet has provided increasing numbers of large data sources as
abasisforanalysiswiththehelpoftechniquesprovidedbydataminingandinformation
retrieval. But not only has the number of data sources multiplied, so has the size and
the complexity.
A particular pertinent aspect of the explosive growth of the Internet is the increasing
utility and dependence upon electronic means of communication. The ease of use, speed
and reliability has been quietly revolutionizing the way people conduct their day to day
business since the inception and application in the latter part of the previous century.
Communication corpora have been considered for some time now. The focus of anal-
ysis has mainly fallen into two camps, the first looking at the structure of the commu-
nication graph, and the second using the content as a basis for information retrieval
techniques to mine previously unknown facets from the data.
It is our opinion that the combination of content with structure can significantly
increase the quality of data extracted as well as increase the flexibility when considering
very large text corpora.
This thesis will focus on the analysis and use of the communication patterns which
can be discovered in the flow of conversations over such electronic media. The focus will
reside primarily on e-mail driven communication, but will be generalized to any form of
communication fitting into description of directed and text-based communication. This
allows a broad spectrum of communication methods to be considered.
iiiABSTRACT
ivContents
Zusammenfassung i
Abstract iii
1 Introduction 1
Starting Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Related Work 3
2.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Definitions and Usage . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.2 Graph Types of Interest . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Network Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Social Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Social Network Analysis . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 An Algorithmic Perspective . . . . . . . . . . . . . . . . . . . . . 18
2.3 Text Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.1 Semantic Content . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.2 Content Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Graph Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Cliques and Cohesive Subgroups . . . . . . . . . . . . . . . . . . . 26
2.4.2 Sub-graph Extraction . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.3 Density Based Graph Mining . . . . . . . . . . . . . . . . . . . . 29
3 Partitioning Massive Graphs 31
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Massive Corpora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Communication Networks . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 E-Mail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.3 Web-logs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.4 Web Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Interpreting SNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
vContents
3.3.1 Treating Massive Graphs . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.2 Mining Graphs for Constraints. . . . . . . . . . . . . . . . . . . . 39
3.4 Spectral Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.1 Topic Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.2 Network Segmentation . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 Content Based