Difference between revisions of "MCSN Tuesday, 25-Oct-11"

From CCE wiki archived
Jump to: navigation, search
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
* Review of quiz and concepts:
+
* Note:
** Density
+
** 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
 
*** # lines divided by # possible lines
 
*** Cannot exceed 100%
 
*** Cannot exceed 100%
** Degree
+
*** Undirected simple network on N vertices contains N*(N-1)/2 possible lines
*** indegree and outdegree
+
*** 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
 
*** total degree: sum over all vertices
*** average degree...
+
*** average degree: divide that sum by the number of vertices
*** ...and a neat trick for computing total and average degree (e.g. if all you know is there are 8 vertices and 8 lines...)
+
*** 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)
** Components
+
** '''Connectivity and Components'''
 
*** criteria:  (a) violate no one-way streets; (b) do not visit any vertex twice.
 
*** criteria:  (a) violate no one-way streets; (b) do not visit any vertex twice.
 
**** path (a,b)
 
**** path (a,b)
Line 28: Line 38:
 
**** 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.
 
**** 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 [http://ccl.northwestern.edu/netlogo/models/GiantComponent beautiful simulation] which illustrates giant component formation in a random graph.
 
**** Try this [http://ccl.northwestern.edu/netlogo/models/GiantComponent beautiful simulation] which illustrates giant component formation in a random graph.
** K-cores
+
** '''K-cores'''
 
*** The k-core is a maximal subnet in which every vertex is degree k  or greater.
 
*** 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 "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 are not necessarily connected
*** a partition is defined by assigning each vertex to its maximum k-core.   
+
*** 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!''
 
*** 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.
 
*** 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.
 
*** OR: find the k-core by  deleting vertices of degree less than k, then repeating.
** Complete networks, triads and cliques
+
** '''Complete networks, triads and cliques'''
*** Complete networks
+
*** Complete networks: A complete network is 100% dense
**** A complete network is 100% dense
+
*** Complete triads
 
**** A complete triad is a triangular complete network ("bone")
 
**** A complete triad is a triangular complete network ("bone")
 
**** Complete triads may overlap  
 
**** Complete triads may overlap  
Line 46: Line 57:
 
**** A partition can be generated by counting, for each vertex, how many triads include it
 
**** A partition can be generated by counting, for each vertex, how many triads include it
 
*** Cliques
 
*** Cliques
*** A clique is a maximal complete subnetwork
+
*** A clique is a ''maximal'' complete subnetwork
 
*** Cliques may overlap
 
*** Cliques may overlap
 
*** Cliques need not cover the network
 
*** Cliques need not cover the network
*** Cliques generally do not form a partition
+
*** Cliques thus generally do not form a partition
 +
* Balance and cluster theory (ch 4)

Latest revision as of 10:06, 25 October 2011

  • 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
      • Complete triads
        • 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 thus generally do not form a partition
  • Balance and cluster theory (ch 4)