Detailansicht
Detecting sets of linked key players in social networks
Marlene Weiß
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Betreuer*in
Walter Gutjahr
DOI
10.25365/thesis.23678
URN
urn:nbn:at:at-ubw:1-29896.37237.184262-6
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In der Analyse sozialer Netzwerke ist der Begriff der Gruppen-Betweenness eine Einheit, welche den Einfluss einer Gruppe innerhalb eines Netzwerks misst. Die Gruppen-Betweenness einer Teilmenge von Individuen in einem sozialen Netzwerk ist umso größer, je mehr kürzeste Pfade zwischen Paaren von anderen Personen im Netzwerk über Mitglieder der betrachteten Teilmenge verlaufen.
Es gibt Algorithmen zur Bestimmung der Gruppen-Betweenness, und auch das Problem der Bestimmung einer Teilmenge gegebener Größe mit maximaler Gruppen-Betweenness wurde in der Literatur bereits behandelt. Das Ziel dieser Arbeit ist aber nicht nur eine Gruppe mit maximalen Gruppen-Betweenness Wert zu finden, sondern auch einen Algorithmus für die Suche nach Gruppen, in der jedes Mitglied mit jedem anderen verbunden ist (sogennante Cliquen), zu entwickeln.
Da das Problem np-schwer ist, ist der entwickelte Algorithmus von metaheuristischer Natur. Zur Qualitätssicherung wurde nicht nur ein Algorithmus angewendet, sondern zwei unterschiedliche Techniken - Simulated Annealing (SA) und Genetischer Algorithmus (GA) - implementiert und verglichen.
Im Zusammenhang mit dieser Problemstellung sind die besten Teilmengen eines Netzwerks nicht zulässig, das heißt sie stellen keine Clique dar. Daher wird ein geeigneter Ansatz benötigt um entweder unzulässige Lösungen wieder auszuscheiden (Penalty Methode) oder aber nur zulässige Lösungen zu generieren (Repair Methode). Die hier vorgestellten Algorithmen basieren auf zwei verschiedenen Penalty-Methoden.
Die der Analyse zugrunde liegenden Daten sind sowohl von realweltlichen sozialen Netzwerken als auch von synthetisch erzeugten Daten abgeleitet.
Abstract
(Englisch)
In Social Network Analysis (SNA) the concept of Group Betweenness Centrality (GBC) is a unit to measure the influence of a group within a network. It is defined as the more shortest paths of the network pass through a subset of individuals, the greater the betweenness of this subset of individuals is.
There are algorithms for determining the Group Betweenness Centrality and also for determining a subset of given size with maximum GBC. However, the aim of this thesis is not only to find a group with maximum GBC, but also to develop an algorithm for finding a group in which every member is connected to every other member (also called clique).
As the problem itself is np-hard the proposed algorithm is of a meta heuristic nature. For quality assessment not only one algorithm was implemented, instead the two techniques Simulated Annealing (SA) and Genetic Algorithm (GA) were applied and compared.
Since most of the generated solutions are not feasible in the context of this problem statement, i.e. don't compose a clique, a suitable approach to either eliminate unacceptable solutions (penalty-function method) or only generate feasible solutions (repair function method), is required. The final algorithms work with two different penalty method approaches.
The underlying data used in the analysis is derived from real-world data sets of social networks as well as from synthetically generated data.
Schlagwörter
Schlagwörter
(Englisch)
social networks social network analysis group betweeness centrality GBC genetic algorithm simulated annealing
Schlagwörter
(Deutsch)
social networks, /social network analysis group betweeness centrality GBC genetic algorithm simulated annealing
Autor*innen
Marlene Weiß
Haupttitel (Englisch)
Detecting sets of linked key players in social networks
Paralleltitel (Englisch)
Detecting sets of linked key players in social networks
Publikationsjahr
2012
Umfangsangabe
81 S.
Sprache
Englisch
Beurteiler*in
Walter Gutjahr
Klassifikation
54 Informatik > 54.99 Informatik: Sonstiges
AC Nummer
AC11044327
Utheses ID
21170
Studienkennzahl
UA | 066 | 926 | |