Difference between revisions of "MCSN Tuesday, 25-Oct-11"
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
− | |||
* Note: | * Note: | ||
** Repeat quiz on Thursday, either to replace or average with last quiz (your choice) | ** Repeat quiz on Thursday, either to replace or average with last quiz (your choice) | ||
Line 8: | Line 7: | ||
---- | ---- | ||
− | * Review of quiz and chapter 3 concepts | + | * Review of quiz and chapter 3 concepts. ''It's very important that you understand this material! Please see me if you do not.'' |
− | + | ** '''Density''' | |
− | ** 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 |
− | *** | + | *** 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 38: | 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 | + | *** 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 |
− | + | *** 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 56: | 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) | * 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.
- 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
- 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
- Density
- Balance and cluster theory (ch 4)