MCSN Tuesday, 25-Oct-11

• Review of quiz and concepts:
  • Density
    • # lines divided by # possible lines
    • Cannot exceed 100%
  • Degree
    • indegree and outdegree
    • total degree: sum over all vertices
    • average degree...
    • ...and a neat trick for computing total and average degree (e.g. if all you know is there are 8 vertices and 8 lines...)
  • Components
    • criteria: (a) violate no one-way streets; (b) do not visit any vertex twice.
      • path (a,b)
      • semipath (not a, b)
      • walk (a, not b)
      • semiwalk (not a, not b)
    • weak
      • a subnet is weakly connected if each pair of vertices is connected by a semipath
      • a weak component is a maximal weakly connected subnet
      • find it by tracing all the vertices semipath-reachable from a particular vertex V
    • strong
      • a subnet is strongly connected if each pair of vertices is connected by a path
      • a strong component is a maximal strongly connected subnet
      • find it by tracing all the vertices path-reachable from a particular vertex V, which can also reach V
    • components never overlap
    • components cover the network
    • components therefore define a partition
    • Giant component formation
      • Play with Pajek: 100 vertices, vary the number of arcs. How many components are there? How big are they? You'll notice with more than 100 arcs that a large component arises.
      • Try this beautiful simulation which illustrates giant component formation in a random graph.
  • K-cores
    • The k-core is a maximal subnet in which every vertex is degree k or greater.
    • k-cores "nest": the 0-core contains the 1-core, which contains the 2-core, which contains the 3-core
    • k-cores are not necessarily connected
    • a partition is defined by assigning each vertex to its maximum k-core.
    • this partition cannot be computed from degree information alone!
    • find the k-core by locating a vertex of degree k or more, then checking if at least k neighbors could be included in the k-core.
    • OR: find the k-core by deleting vertices of degree less than k, then repeating.
  • Complete networks, triads and cliques
    • Complete networks
      • A complete network is 100% dense
      • A complete triad is a triangular complete network ("bone")
      • Complete triads may overlap
      • The set of complete triads ("skeleton") may have several components
      • Each component is considered a "social circle"
      • Complete triads do not form a partition
      • A partition can be generated by counting, for each vertex, how many triads include it
    • Cliques
    • A clique is a maximal complete subnetwork
    • Cliques may overlap
    • Cliques need not cover the network
    • Cliques generally do not form a partition