Lade Inhalt...

Finding a team of experts in social networks. Algorithmen und Experimente zum Teambildungsproblem

Hausarbeit 2010 16 Seiten

Informatik - Internet, neue Technologien

Leseprobe

Inhaltsverzeichnis

Abbildungsverzeichnis

Einleitung

1. Annahmen, Problemstellung und Diskussion

2. Algorithmen

3. Experimente und Bewertungen

Fazit

Abbildungsverzeichnis

Abbildung 1: Netzwerk der Verbindungen zwischen den Personen in {a,b,c,d,e}

Abbildung 2: Durchschnittliche Cc-R-Kosten von T (t,1)

Abbildung 3: Durchschnittliche Cc-MST-Kosten von T(t,1)

Abbildung 4: Kardinalitätsanalyse

Einleitung

Heutzutage ist man sich darüber im Klaren, dass Erfolg eines Projektes nicht nur davon abhängig ist, welche Personen daran beteiligt sind, sondern viel mehr davon, ob diese effektiv miteinander kollaborieren, kommunizieren und als ein Team erfolgreich zusammen arbeiten können. Auf Grund dessen wird immer häufiger die Frage gestellt, wie man ein Team von Experten bilden kann, die zueinander passen würden und in der Lage wären, eine bestimmte Aufgabe zu lösen bzw. ein Projekt zu führen.

Das Ziel dieser Ausarbeitung ist es, die oben genannte Frage zu beantworten, das Teambildungsproblem zu besprechen, die dazugehörigen Algorithmen und Experimente zu präsentieren und die Schlussfolgerungen in diesem Hinblick zu ziehen.

Als Startpunkt wird folgende Ausgangssituation analysiert: es seien eine Aufgabe T, eine Menge der Personen X, die über bestimmte berufliche Qualifikationen bzw. Eigenschaften verfügen und ein soziales Netzwerk G gegeben, in dem diese Personen organisiert sind.

Es wird diesbezüglich auf das sog. „Teambildungsproblem“ eingegangen - das Problem der Suche nach X ´ - einer Teilmenge von X. Es ist von zentraler Bedeutung, dass die Mitglieder von X ´ nicht nur den Anforderungen der Aufgabe entsprechen, sondern auch effektiv als Team zusammenarbeiten können. Die Effektivität wird mithilfe von Kommunikationskosten gemessen, die in dem Teil des Graphen G entstehen, welcher nur die Knoten der Teilmenge X ´ enthält.

Um sich mit dem Teambildungsproblem auseinandersetzen zu können, müssen zwei Varianten von diesem Problem für zwei verschiedene KommunikationskostenFunktionen erforscht werden.

Um das Teambildungsproblem im Bezug auf ein soziales Netzwerk näher zu erforschen und dabei nützliche und intuitive Ergebnisse zu erzielen werden auch einige Experimente an Dataset von DBLP durchgeführt werden, zwecks der Veranschaulichung der Praxisbezogenheit der Algorithmen.

Im ersten Teil dieser Ausarbeitung werden die Annahmen festgesetzt, das Teambildungsproblem wird genauer definiert und es wird teilweise auf Graphentheorie eingegangen.

Im zweiten Teil werden die Algorithmen zur Lösung des Teambildungsproblems präsentiert und die daraus folgenden Behauptungen untersucht und bewiesen. Der dritte Teil befasst sich mit den praktischen Experimenten und deren Bewertungen im Hinblick auf die dargestellten Algorithmen

1. Annahmen, Problemstellung und Diskussion

Realisierung eines Projekts und Kommunikation zwischen den daran beteiligten Mitarbeitern stehen im großen Zusammenhang zueinander. Ein IT - Manager beschäftigt sich beispielsweise damit, ein Team von Experten für ein Projekt T aus den Bereichen T={algorithms, software engineering, distributed systems, web programming} zu bilden und ihm stehen fünf Kandidaten mit folgenden Eigenschaften zur Verfügung:

X a ={algorithms}, X b ={web programming}, X c ={softwareengineering, distributed systems}, X d ={software engineering} und X e ={software engineering, distributed systems, web programming }. Die Verbindungen zwischen den Kandidaten können in einem sozialen Netzwerk (Abb.1) dargestellt werden:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Netzwerk der Verbindungen zwischen den Personen in {a,b,c,d,e}

Jede Kante zwischen zwei Knoten in dem Graphen G zeigt, dass die damit verbundenen Personen effektiv miteinander kollaborieren können. Ohne Effektivitätsprüfung würde der Projektleiter mit hoher Wahrscheinlichkeit sich für zwei Teams X ´ ={a, b, c} und X ´´ ={a, e} entscheiden, weil beide Teams über notwendige Qualifikationen verfügen. Die Existenz von dem Graphen weist hingegen darauf hin, dass das Team X ´ ={a, b, c} eine bessere Lösung wäre, da zwischen den Kandidaten a und c keine Zusammenarbeit möglich ist.

Soziale Netzwerke sind im Alltag weit verbreitet und durch mehrere Arten vertreten. In einem Unternehmen kann ein soziales Netzwerk das Organigramm bzw. den Stellenplan präsentieren und beweisen, dass die Mitarbeiter aus derselben Abteilung leichter miteinander kommunizieren können, als die Mitarbeiter, die in verschiedenen Abteilungen oder Filialen beschäftigt sind. In der Wissenschafts-community können durch ein Netzwerk beispielsweise die Publikationen dargestellt werden, welche die Wissenschaftler zusammen geschrieben haben. Als andere Beispiele sind auch mehrere professionelle Online-Netzwerke wie www.linkedin.com, www.xing.com usw. zu erwähnen.

Es wird angenommen, dass es eine Aufgabe T, die bestimmte Qualifikationen A={a 1 , ..., a m } voraussetzt und ein Kandidaten-Pool X bestehend aus n Kandidaten X={1, ..., n} existieren und jeder Kandidat i über eine Menge der Eigenschaften bzw. Qualifikationen X i verfügt. Das Ziel ist es, eine Gruppe X ´X zu finden, sodass es in X ´ im Endeffekt mindestens einen Kandidaten gibt, welcher alle vorausgesetzten Qualifikationen besitzt.

Die Kandidaten sind in einem gewichteten und ungerichteten Graphen G (X, E) geordnet, die Kantengewichte werden wie folgt interpretiert: kleinere Kantengewichte zwischen den Knoten i und j zeigen, dass die Kandidaten i und j optimaler miteinander kollaborieren und erfolgreicher zusammen arbeiten können, als die Kandidaten, deren Kantenwerte in dem Graphen G höher sind. Das gesuchte Team sollte in einem Teilgraphen organisiert werden und die Effektivität des Teams wird mithilfe der Kommunikationskosten gemessen.

Die Aufgabe T kann somit als eine Menge der Eigenschaften definiert werden, die für die Lösung dieser Aufgabe erforderlich sind (TA) und wenn es eine Eigenschaft a j in der Menge T liegen sollte (a jT), dann kann es behauptet werden, dass die Qualifikation a j für diese Aufgabe relevant ist. An der Stelle ist ebenfalls die Deckung für die Personenmenge X ´ im Bezug auf die Aufgabe T zu definieren C (X ´ ,T): es handelt sich hierbei um eine Menge der Eigenschaften, die erforderlich sind, um die o.g. Aufgabe zu erledigen und es in der Personenmenge X ´ mindestens eine Person existiert, welche diese Qualifikationen bzw. Fähigkeiten besitzt: C (X ´ , T) = T ∩(∪ ix ´ X i).

Für jede Eigenschaft a wird ein Support S (a) definiert, eine Menge der Personen, welche diese Eigenschaften haben: S (a) = { i | i X und a X i }. Wie bereits erwähnt, sind die Kandidaten in einem gewichteten und ungerichteten Graphen G (X, E) organisiert. Jeder Knoten in dem Graphen G entspricht einem Kandidaten aus dem Kandidaten-Pool X und E ist die Menge der verbindenden und gewichteten Kanten. Das Kantengewicht repräsentiert die Kommunikationskosten zwischen den Knoten bzw. Kandidaten. Für jede zwei Knoten i, i ´X in dem Graphen G (X, E) wird eine Distanzfunktion d (i, i ´) bestimmt als das Gewicht von dem kürzesten Pfad zwischen den Knoten i und i ´. Abgesehen davon sollte auch die Distanz von dem Knoten i X und der Knotenmenge X ´X als d (i, X ´) = min i ´X ´ d (i, i ´) definiert werden.

Anschließend wird der Graph G [ X ´ ] als Teilgraph des Graphen G (X, E) präsentiert, der nur die Knoten aus der Menge X´ enthält.

Das Teambildungsproblem: Gegeben seien eine Personenmenge X bestehend aus n Mitglieder (X = { 1, ...,n }), ein Graph G (X, E) und eine Aufgabe T. Es wird nach einer Personengruppe X ´ aus dem Kandidaten-Pool X (X ´X) gesucht, sodass C (X ´ , T) = T und die Kommunikationskosten sind minimiert.

In dieser Ausarbeitung wird es auf zwei Teambildungsprobleme im Hinblick auf die Kommunikationskosten eingegangen:

1. Diameter - Teambildungsproblem: in diesem Fall werden die Kommunikationskosten mittels Diameter des Graphen G (DiameterKommunikationskosten: Cc-R(X ´)) beschrieben. Der Diameter eines Graphen ist die längste kürzeste Entfernung, die für zwei Knotenpunkte des Graphen auftritt.

2. Minimaler Spannbaum - Teambildungsproblem: die Kommunikationskosten werden dabei als Summe der Kantengewichte des minimalen Spannbaums von dem Graphen G (Minimaler Spannbaum-Kommunikationskosten: Cc-Mst (X ´)) berechnet. Ein Spannbaum heißt minimal, falls kein anderer Spannbaum mit kleinerem Gewicht in diesem Graphen existiert.

In der Definition des Teambildungsproblems und dessen Spezialisierungen wurde es auf Minimierung der Kommunikationskosten zwischen den Teammitglieder eingegangen. Andere Definitionen der Effektivität führen zu den verschiedenen Optimierungsfunktionen. Wenn es die Kommunikationskosten beispielsweise nicht berücksichtigt werden sollten, dann wäre das Ziel eine Personengruppe X ´X zu finden, sodass C (X ´, T) = T und | X ´| minimal ist. Diese Problemstellung ignoriert jedoch die Existenz von dem Teilgraphen G (X ´).

Bei der Optimierung von der Kardinalität des Teams und der Kommunikationskosten zwischen den Team-Mitglieder wäre die Minimierung der Funktion α . | X ′| + (1-α) . Cc (X ′, G) mit α ∈ [0,1] erforderlich. Bei α = 1 wird es nach einem Team mit der minimalen Kardinalität gesucht und bei α = 0 handelt es sich um ein Teambildungsproblem und es ist kompliziert zu bewerten, ob eine solche Optimierung sinnvoll ist, da die Werte in verschiedenen Skalenwerten liegen.

Alternativ können sowohl die Anzahl der Teammitglieder, als auch die Kommunikationskosten zeitgleich betrachtet werden, wenn das Teambildungsproblem als ein bi-objektives Optimierungsproblem definiert wird. Das Ziel wäre in diesem Fall eine optimale multikriterielle Pareto-Optimierung für beide Problemmstellungen zu finden, d.h. eine optimale Lösung, soweit keine vorteilhaftere Lösung vorliegt.

Obwohl die bi-objektive Version des Problems in dieser Ausarbeitung nicht berücksichtigt wird, ist es nichtsdestotrotz anzunehmen, dass die minimalen Kommunikationskosten mehr für kleinere und höhere Kommunikationskosten für größere Teams typisch sind.

Wie es in der Annahme bereits erwähnt, jeder Kandidat X i aus dem Kandidatenpool X unbedingt einige Qualifikationen besitzt und die Aufgabe T setzt eine bestimmte Menge der Eigenschaften voraus, die erforderlich sind, um diese Aufgabe zu erledigen und es wird nicht diskutiert, inwiefern jede einzelne Fähigkeit hierfür relevant ist. Im Allgemeinen können die Kompetenz einer Person und der Umfang, in dem eine bestimmte Fähigkeit für die Erfüllung der Aufgabe relevant ist als eine Reihe der ganzen Zahlen {0,1,...,δ} modelliert werden. Diesbezüglich werden sowohl das Kompetenzniveau, als auch Aufgabenbereich genauer analysiert und dadurch werden nur solche Kandidaten in Anspruch genommen, dessen Kompetenz entweder gleich, oder höher ist als es für die Erfüllung der Aufgabe erforderlich ist.

2. Algorithmen

In diesem Abschnitt werden die Algorithmen für das DiameterTeambildungsproblem (R-TF), sowie für das Minimaler-Spannbaum- Teambildungsproblem (MST-TF) dargestellt.

Algorithmus 1 präsentiert den Pseudocode von dem RarestFirst-Algorithmus für das Diameter - Teambildungsproblem:

Input: G(X,E), Vectors {X 1 ,...,X n }, T Output: X ´X, G[X ´ ]

1.for every aT do
2. S(a)={i| aX i }
3 .a rare ← arg mina∈ T |A(a)|
4.for every iS (arare) do
5. for aT and aa rare do
6. R i a ← d (i,S(a))
7. R i ← maxa R ia
8. i* ← arg min R i
9. X ´ =i* ∪ { Path (i*,S(a))|aT }

Am Anfang wird für jede Eigenschaft, welche für die Erfüllung der Aufgabe bedeutend ist, ein Support (S (a)) berechnet. Nachfolgend wird eine Eigenschaft mit minimaler Kardinalität ausgewählt: S (a rare). Aus dem Kandidatenpool wird anschließend eine Person ausgewählt, die zu dem Graphen mit dem minimalen Diameter führt. Linie 6 zeigt, dass die Distanz d (i, S (a)) minimal ist: min i ´S(a) d (i, i ´) ist und der Pfad (i*, S (a)) aus der Linie 9 ist ein Knoten-set mit dem kürzesten Weg von i* zu i ´, wo i ´S (a) und d (i*, S (a)) = d (i* ,i ´). Alle kürzeste Wege wurden paarweise vorgerechnet und in Hash-Tabellen gespeichert. Die Laufzeit des RarestFirst-Algorithmus ist O (| S (a rare)|× n), oder O (n ²) im schlimmsten Fall, was in der Praxis eigentlich nicht vorkommen kann.

Für jede Distanzfunktion d, welche der Dreiecksungleichung entspricht, sind die Diameter - Kommunikationskosten für die Lösung X ´ aus dem RarestFirstAlgorithmus doppelt so hoch als die Diameter - Kommunikationskosten für eine optimale Lösung X*: Cc-R (X ´) ≤ 2 . Cc - R (X*);

Diese Behauptung kann bewiesen werden, in dem es auf die Lösung am Ausgang des RarestFirst-Algorithmus eingegangen wird: a rareT wäre dabei eine Eigenschaft der letzten Personenanzahl aus der Menge X und i* eine aus dem Kandidaten-Set S (a rare) ausgewählte Person, die in der Personenmenge X ´ enthalten ist. Nachfolgend werden zwei andere Eigenschaften aa ´a rare und ebenso zwei Personen i, i ´X ´ überprüft, sodass iS (a), iS (a ´).

[...]

Details

Seiten
16
Jahr
2010
ISBN (eBook)
9783656937715
ISBN (Buch)
9783656937722
Dateigröße
1.1 MB
Sprache
Deutsch
Katalognummer
v295823
Institution / Hochschule
Universität Trier
Note
3.0
Schlagworte
finding algorithmen experimente teambildungsproblem

Autor

Teilen

Zurück

Titel: Finding a team of experts in social networks. Algorithmen und Experimente zum Teambildungsproblem