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
- criteria: (a) violate no one-way streets; (b) do not visit any vertex twice.
- 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.
- Cliques and complete subnetworks
- Density