Please enable JavaScript.

Coggle requires JavaScript to display documents.

Graph Theory 2 (Trees (characterization (theorem1 (if G is connected, then…

- - - - if G is connected, then n <= e +1
    - - a connected graph G with n vertices and n-1 edges is a tree
    - - a simple graph G is a tree iff for all u,v vertices there exist a unique (u,v)-path
    - - a connected graph G is a tree iff every edge is a cut edge
  - - - a tree T in G is a spanning tree of G if V(T) = V(G)
    - - definition
        
        if G is weighted, a spanning tree is minimal if the sum of the weights of its edges is minimal
      - lemma
        
        T is a ST of G and e an edge in E(G) \ E(T), then H = T U {e} contains a cycle
      - lemma (joining fragment)
        
        if G is weighted connected, V1 and V2 2 non empty paritions of V(G). e is an edge in G with minimum weight linking V1 and V2. Then there is a MST of G containing e.
      - Kruskal algorithm
        
        G connected. Initially each vertex is a separate subtree. In each step, an edge of lowest weight is used to join 2 subtrees (without creating cycles). Do that until all vertices are connected.
      - lemma (weighted graph with unique weights)
        
        G weighted graph with distinct weights. T is a MST for G and S a subtree of T. If e is the lowest-weight outgoing edge of S (incident to exactly one vertex in S) then e is in E(T)
    - - each vertex v keeps a routing table Rv
        
        if Rv[u] = w then messages from v to u are sent to w
      - messages to u should follow a path along a ST rooted at u
        
        a tree optimized for all (v-u)-paths is a sink tree
      - Dijkstra's algorithm
        
        compute the sink tree rooted at a vertex u in a weighted graph (with nonnegative weights)
        
        d(x) is the distance from x to u, n(x) the next vertex after x on this path (F is none)
        
        algorithm
        
        d(u) = 0, d(v) = inf for all v != u
        n(v) = F for all vertices
        H contains all vertices, S is empty
        While H is non-empty:
        
        remove a vertex v from H with the smallest d-value and add it to S
        
        for each x in Nin(v) inter H if w(<x,v>) + d(v) < d(x) then d(x) <- w(<x,v>) + d(v) and n(x) <- v
        
        when H is empty the n-values constitute a sink tree and the d-values the weights of shortest paths
      - Bellman-Ford
        
        compute the shortest paths from all vertices to a vertex u in a weighted graph (weights can be negative)
        
        algorithm
        
        for i= 1 to n-1 do:
        for each arc <x,v> do
        if w(<x,v>)+d(v) < d(x) then
        d(x) <- w(<x,v>) + d(v)
        n(x) <- v
        for each arc <x,v> do
        if w(<x,v>) + d(v) < d(x) then
        return "graph contains a negative-weight cycle"
        
        complexity: O(mn)
- - - - d(u,v) = length of a shortest (u,v)-path
      - average length of shortest for a vertex u avgD(u) =
      - average path length avgD(G) =
      - characteristic path length
        
        median over all avgD(u)
    - - e(u) = max{d(u,v) | v in V(G)}
    - - rad(G) = min{e(u) | u in V(G)}
    - - diam(G) = max{d(u,v) | u,v in V(G)}
        diam(G) = max(e(u) | u in V(G)}
  - - - don't consider vertices with deg(v) < 1:
        V* = {v in V(G) | deg(v) > 1}
      - CC(G) =
      - triangle in a graph = complete subgraph of 3 vertices
      - triple in a graph = subgraph of 3 vertices and 2 edges
      - network transitivity tau(G) =
        ntriangle = number of distinct triangles in G
        ntriple = number of distinct triples in G
      - triangle/triple at v means v is the middle
        
        number triangle in G = 1/3(sum triangles at v for v in V(G))
        
        number of triple at v = deg(v) choose 2
        
        cc(v) = N triangles(v) / N triples(v)
  - - - C(G) = set of minimal eccentricity
        C(G) = {v in V(G) | e(v) = rad(G)}
      - at the center = at minimal distance to the farthest vertex.
        the higher the centrality the closer to the center of the graph
    - - Ce(u) = 1/e(u)
    - - S(x,y) set of shortest paths between x and y
        S(x,u,y) set of shortest paths that pass through u
      - Cb(u) =
    - - Cc(u) =
      - how close is a vertex to all other vertices
- - - - clustering coefficient of any vertex is p
  - - - algorithm
        
        V = {v1, v2, ... vn}
        n >> k >> ln(n) >> 1 with k even
        
        construct Harary graph Hk,n
        
        considering each edge <u,v> in Hk,n only once, for each vertex u, replace <u,v> by <u,w> where w != u is in V - N(u) with a probability of p
        
        result: WS(n,k,p)
      - low average shortest path length because of the weak links created with a probability of p
      - WS(n,k,0) = Harary graph Hk,n
        
        CC(G) = 0.75 for any G in WS(n,k,0)
      - theorem2
        
        for all graphs WS(n,k,0) the average shortest path length from u to any other vertex is roughly avgD(u) = n/2k
      - p = 0.05 is a good value for a high clustering coefficient and a low average path length
  - - - algorithm1
        
        start with G in ER(n0,p) and V=V(G). Let n >> n0.
        While |V| < n do:
        
        V <- V U {v} for some vertex v
        
        add edges <v,u> for m <= n0 distinct vertices u in V-{v}
        each u is chosen with a probability proportional to its degree:
        
        Result is a BA(n,n0,m) graph
        
        degree distribution of a BA(n,n0,m):
        
        drawback: the alpha of the power distribution is constant = 3
      - algorithm2 (generalized BA-graphs)
        
        start with G in ER(n0,p) and V=V(G).
        While |V|<n do:
        
        V<-VU{v} for some vertex v
        
        add edges <v,u> for m <= n0 distinct vertices u in V-{v}. Each u is chosen with probability proportional to deg(u)
        
        for a constant c >= 0, add cm edges between vertices in V-{v}. The probability to add an edge <x,y> is proportional to deg(x)deg(y)
        
        if c = 0 this is a standard BA graph
        
        degree distribution of a generalized BA(n,n0,m):
      - average shortest path lengths
        
        shortest path length lower than ER graph due to the presence of hubs.
      - algorithm3 (tunable clustering coefficient)
        
        Start with a set of n0 vertices, no edges.
        While |V|<n do:
        
        V<-VU{v} for some new vertex v
        
        add m edges as follows:
        
        pick a u != v non adjacent to v with probability proportional to deg(u). Add edge <u,v>
        
        with probability 1 - q redo the previous step. Else select w != v adjacent to u but not to v (if no such vertex exists redo previous step). Add edge <w,v> and repeat this step
        
        degree distribution is a power law with alpha = 3
        
        if we increase q, we increase the clustering coefficient
      - clustering coefficient higher than for an ER graph but still low
- - - - degree distribution:
    - - use hyperlinks to a page p as a criterion for the importance
      - d in [0,1) is a constant (d=0.85 for Google)
      - Page rank algorithm:
        
        Let V = {v1,v2...vn}, t = 0, d = 0.85 (damping factor):
        
        set PR(vi,t) = 1/n for all vi in V
        
        for all vi in V calculate:
        PR(vi,t+1)=
        
        Increment t of one unit
        
        Go to step 2 unless we reached a max num of iteration or:
        
        the page rank distribution follow a power law:
  - - - let D be a digraph with n vertices
      - influence domain R-(v) of vertex v
        
        set of vertices which v can reached
        
        {u in V(D) - v | there exists a (u,v)-path}
      - proximity prestige pprox(v):
        =
        fraction of vertices that can reach v, divided by the average distance of these vertices to v
    - - digraph with 'adjacency matrix' A:
        
        and for each vertex u
        A[v,u] expresses how much v is appreciated by u
      - definition
        
        prank(v) =
        
        The importance of A[v,u] depends on prank(u)
    - - triad
        
        relationship between a triple of social entities
      - signed graph
        
        definition
        
        each edge e is labeled with either a positive '+' of a negative '-' sign: sign(e)
        
        sign of a walk T
        
        product of the signs of its edges
        sign(T) =
        
        balanced sign graphs
        
        a sign graph is balanced if all its cycles are positive
        
        theorem (Harary)
        
        a signed graph G is balanced iff V(G) can be partitioned into 2 disjoint subsets V0 and V1 such that:
        
        each negative edge is incident to a vertex from V0 and from V1
        
        each positive edge is incident to vertices from the same set
        
        partition algorithm for balanced graphs
        
        Select an arbitrary u in V(G) and initialize V0 <- {u} , V1 <- {} and I <- {}
        Whlile I != V0 U V1, select a v in (V0 U V1)-I and assume that v is in Vi (i= 0 or 1)
        
        Vi <- Vi U {w} for all positive edges <v,w>
        
        V1-i <- V1-i U {w} for all negative edges <v,w>
        
        I <- I U {v}
      - affiliation networks
        
        idea
        
        people are tied together through membership relations.
        
        Social structures consists of actors (VA) and events (VE)
        actors participate in events
        
        representation
        
        bipartite graph with 2 sets of vertices VA (actors) and VE (events)
        
        edge <a,e> represents that actor a participates in event e
        
        Adjacency submatrix AE
        
        AE[a,e]=1 iff actor a participated in event e
        
        special tables
        
        Number of events in which actors a and b both participate
        
        =
        
        diagonal = number of event that a particular actor participated in
        
        Number of actors that participate in events e and f
        
        =
        
        diagonal = number of actors that participated in a particular event