# MCSN Tuesday, 25-Oct-11

(diff) ?Older revision | view current revision (diff) | Newer revision? (diff)
• Note:
• Repeat quiz on Thursday, either to replace or average with last quiz (your choice)
• Draft proposals are also due Thursday
• 4.8 due today
• Open Quiz#2.paj

• Review of quiz and chapter 3 concepts. It's very important that you understand this material! Please see me if you do not.
• Density
• # lines divided by # possible lines
• Cannot exceed 100%
• Undirected simple network on N vertices contains N*(N-1)/2 possible lines
• Directed simple network on N vertices contains N*N possible lines (if loops are allowed) or N*(N-1) possible lines (if loops are expressly disallowed)
• Degree
• degree (undirected network); indegree and outdegree (directed network)
• total degree: sum over all vertices
• average degree: divide that sum by the number of vertices
• There's a neat trick for computing total and average degree (especially if all you know is the number of vertices and the number of lines, but don't know how they're connected)
• Connectivity and 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
• k-cores themselves do not form a partition
• a partition can be 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