VL 3.1 Centrality Flashcards
Graohen sind allgegenwärtig! Nennen sie ein paar Beispiele!
#Soziale Netzwerke (SN), #Web Graphen, #Chemische (Struktur-) Formeln, #(Schematische) Karten (Netzpläne), #Prozess- und Programmausführungen.
[mP] Formeln für Zentralitätsmaße, die in der Vorlesung explizit vorgestellt wurden, zusammen mit Erläuterung der entsprechenden Intuition.
da Bilder einfügen! rest Erklärung sollte easy sein
Was ist der damping factor d der PR-Formel -> naja auch Knoten, auf die keiner verweist sollen einen minimalen PR bekommen. üblicherweise d=0,9
Wert von 0 für Knoten auf die keiner verweist würde Berechnungen schwierig machen!
Also: alle Knoten haben einen pos. PageRank
[mP] Klassifikation der Zentralitätsmasse aus Vorlesung wiedergeben können.
Zentralitätsansätze/Klassifikation
Lokale Ansätze #Betrachten nur die direkte Nachbarschaft eines Knoten #InDegree
Eigenvektor-basierte Ansätze
#Rekursiv-definierte Kennzahl, berücksichtigt direkte und indirekte Nachbarschaft #PageRank, Authority (HITS), Positional Weakness Function
Distanz-basierte Ansätze #Kürzeste Wege (shortest path) zwischen zwei Knoten #Proximity Prestige, Integration
[mP] Parametrisierung unseres Centrality-Operators erklären können. (Warum muss das so mächtig sein?)
Definition des Operators:
CENTRALITYattr, Av, As, At, Aw, Measure
Mit Measure : Zentralitätsmaß: z.b InDegree,PageRank etc.
Warum nochmal Relationen Rverticies und Redges?
–> möglicherweise hat ein Knoten keine eingehenden oder ausgehende Kante hat, diese Info wird aber für die Zentralitätsberechnung ggf. benötigt
attr: neue Attribut, das den berechneten Zentralitätswert enhält
Av =
As = Attribut inerhalb von Redges, das den Ausgangsknoten der Kante identifiziert
At = Attribut inerhalb von Redges, das den Zielsknoten der Kante identifiziert
Aw = Attribut, das mit gewichteten Kanten umgehen kann
Bsp siehe Bild
CENTRALITY[PageRank, ID, Recommender, Recommendee, Value, PageRank]
(Entity, Recommendation)
Erweiterung durch eigene Operatoren zusätzlich zu den Algebra Operatoren! (z.b TOP und MAP)
Top Operator: TOPk,attr
Gibt die k Tupel mit dem höchsten Wert in Bezug auf attr zurück (nicht notwendigerweise sortiert)
Example:
–> Bild
Wie ist ein Graph aufgebaut? Bestandteile?
Graph G := (V, E)
geordnetes Paar der Mengen V und E. V – Menge der Knoten (Vertices). E – Menge der Kanten (Edges)
(-> V und E sind disjunkt.)
Warum stößt man mit SQL bei Informationsbedürfnissen schnell an Grenzen?d
Knackpunkte: Lassen sich alle relevanten Informationsbedürfnisse in SQL formulieren? Wie effizient ist die Anfrageverarbeitung?
Komplexere Informationsbedürfnisse, mit weniger klarer Implementierung „Welche Teilnehmer sind wichtig oder einflussreich?“ „Welche Teilnehmer sind (in irgendeiner Weise) auffällig?“ „Gibt es Gruppen ähnlicher Teilnehmer?“
Unterscheidung verhaltensbasiert und strukturell?
Unterscheidung
verhaltensbasiert[im folgenden (trust)Policies] (=Interaktionen werden durch Kanten repräsentiert / Bsp. pos. Feedback von jmd. eine Kante)
Oft mit Aggregation, Sortieren usw. verbunden
und
strukturell (=Professoren haben Moderatorprivilegien u. Masterstudenten nicht)
Was sind die Vorraussetzungen um komplexe Informationsbedürfnisse aus verhaltensbasierten (trustPoliceis) Aktionen zu befriedigen?
Voraussetzung 1: Trust policies können komplexe Informationsbedürfnisse enthalten, z.B., aggregation (‘average feedback’).
Voraussetzung 2: Adäquate Repräsentation des Verhaltenwissens (behavior-specific knowledge),welches das gesuchte Verhalten beschreibt.
–>Unterschiedliche Verhaltenswissen-Typen (behavior-specific knowledge types): feedback, reputation, recommendation, trust.
Erkläre die Verhaltenswissens-Typen von Trust Policies!
Verhaltenswissen-Typen (1)
Feedback Bewertung einer (Inter-)Aktion eines Partners (ratee) durch einen Bewerter (rater) Alice: “Beim letzten Kauf bei Bob, war alles in Ordnung.“ 10 / 10 Punkte
Recommendation
Meinung eines Partners / einer Institution (recommendee) über zurückliegende Verhalten eines (anderen) Partners Alice: “Als Seminarpartner, kann ich Bob wärmstens empfehlen.”
Reputation
Gesamthafte Meinung des Netzwerkes in Bezug auf einen Teilnehmer Globale Eigenschaft. Example: “Als Verhandlungsführer, hat Bob eine exzellente Reputation. “
Trust
(Anteiliges) Vertauen eines Partners/ einer Institution (truster), dass sich ein Partner (trustee) in Bezug auf eine oder mehrere Interaktionen wie gewünscht verhält. Alice: “Ich vertraue Bob bezüglich Z.”
Wie kann man den InDegree aushebeln und wann ist er nützlich?
Funktioniert bei großen SN - z.b FaceBook
-> like Button für Seiten ist InDegree
Wenn Manipulation möglich, dann kann man InDegree leicht beeinflussen! –> Fake-Accounts liken die Seite
Erkläre Proximity Prestige!
(*mP)Was ist der maximale (minimale) Wert von Pp (und wann)?
Maß aus der Kategorie Distanz-basiert:
Idee: Wie gut ein Knoten von den anderen Knoten im Graph erreichbar ist
Erreichbarkeit (zweierlei)
(1) Es gibt von vielen anderen Knoten des Graphen einen Pfad zu mir, besser als von wenigen Knoten ein Pfad zu mir
ALSO: Von wie vielen Knoten kann ich über einen Pfad zu mir kommen
(2) Wie lang sind diese Pfade? Kurze Pfade sind besser
Zähler: Anzahl der anderen Knoten die mich erreichen durch alle Knoten im Graph (Relative Größe der Influence Domain)
Nenner: Durchschnittliche kürzeste-Pfadlänge zu mir
Formel –> Bild
(*mP) maximal wenn –> hub-artiger Graph = ich in der Mitte und von allen anderen Knoten gibt es eine Kante zu mir
minimal wenn –> Ii (Influence Domain) = leer also 0, durch 0 teilen gibt 0 BZW. Ii klein und Pfade lang
Erkläre Betweenes Centrality!
(mP) Wann ist betweenness centrality maximal?
(mP)Beispiel wo sich die beiden Zentralitätsmaße unterscheiden?
Informell: Wie oft ich (als Knoten) zwischen anderen Knoten bin
A und B besprechen was, aber C (ich) liegt zwischen beiden. Also bekommt C mit was besprochen wird “haha”. Aus sich von C ist das gut
Angenommen aber es gibt viele Pfade von A nach B und nur ein Pfad geht dabei über C. Naja dann ist die Betweenes Centrality von C “nicht so toll”
Gibt es nur einen Pfad, des dann auch über C führt ist das “das beste”
ALSO: Beschreibt nicht Erreichbarkeit, sondern eher Informiertheit!
(*mP) Sternförmiger Graph –> Hub bzw Triad?!
Bei Proximity Prestige war es der Stern (Hub) und hier auch?! Was ist der Unterschied?
(*mP)Beispiel wo sich die beiden Zentralitätsmaße unterscheiden?
Beispiel: (1) Auswirkung auf Bc aber nicht auf Proximity Prestige
Formel –> Bild + Bild(1) VL
Wie kann man die Zentralitätsmaße ausgeklügelter verwenden?
Ausgeklügelter:
Die Zentralitätsmaße als Grundlage für weitere Berechnungen nehmen
–> Gegeben die Top10 Teilnehmer mit der höchsten Zentralität –> Was ist die durchschn. Pfadlänge zwischen diesen Top10-Leuten
Wie groß ist die durchschnittliche Pfadlänge zwischen Individuen mit hoher Zentralität?
(verglichen mit dem von zwei zufällig gewählten)?
Stehen sich Individuen, die gut vernetzt sind im allgemeinen nahe?
In diesem Fall ist Zentralität ein Selektionskriterium, würde also in der Where oder Having Klausel erscheinen
Also: erst Zentralitätsberechnung und dann darauf aufbauen weitere Berechungen
Oder aber anders herum!
Gegeben zwei SN:
A ist LinkedIn graph.
A‘ ist projection des LinkedIn Graph – nur Frauen, die mit einander Verbunden sind.
Welche Frauen haben in A‘ eine signifikant höhere Zentralität als in A? Sind also unter Frauen besser vernetzt als im allgemeinen?
ALSO: Welche Frauen nutzen hauptsächlich Männer um sich zu vernetzen vs. welche Frauen sind hauptsächlich auf ihr Frauennetzwerk gestützt?
Unterschied zu vorhin –> erst Graph A´ konstruiert (onlyFrauenGraph) und dann Zentralität berechnet
Unten –> (1) Berechnung (2) Zentralität
Oben umgekert –> (1) Zentralität (2) weitere Berechnung
–> Worauf will Böhm hinaus: Zentalitätsmaß sollte elementares Konstrukt bei der Anfrage sein und lässt sich an beliebiger Stelle einsetzen
(*mP) Was könnte der Vergleich unterschiedlicher Zentralitätsmaße bringen?
Weitere Möglichkeiten
Welche Personen haben signifikant unterschiedliche Werte für Zentralitätsmaße A and B?
Z.B., A=hohe Proximity und B=niedrige Betweenness.
=> Persons die gut vernetzt sind, aber wenig Einfluss haben.
Oder, A=niedrige Proximity und B=hoher InDegree, => viele Kontakte, aber nicht wichtig
ALSO: Unterschiedliche Zentralitätsmaße haben auch eine Darseinsberechtigung und können z.b solche Informationsbedürfnisse befriedigen!
Wie verhält es sich wenn die unterschiedlich klassifizierten Centralitätsmaße auf verschiedene Graph-Typen angewendet werden. Wann besteht eine Anwendbarkein und wann nicht?
Was muss man für die Anwendbarkeit tun wenn Anwendbarkeit erstmal nicht gegeben ist und was ist das Problem dabei?
Bild
Graph transformieren –> z.b mehrere Kanten von A nach B durch eine Kante ersetzten –> bzw um ganz nach rechts in der Grafik zu kommen gewichtete kanten durch ungewichtete ersetzen!
Was ist das Problem dabei?
Wie man das macht ist nicht standardisiert
- -> Informationsverlust
- -> Frage nach dem Schwellenwert? Wann fällt die Kante ganz weg wie im Beispiel?
Bild
