Consider the G(N,m) model of random graphs, with the settings N=5 and m a function of N, specifically m=(0.4)*N. Draw any specific graph that could be generated by this model.
Full credit for any graph with 5 vertices and 2 edges. 1 point if the graph has 5 vertices.
This question refers to Malcolm Gladwell's book The Tipping Point. Draw lines to match the types of individual (on the left) with the attributes that characterize individuals of that sort (on the right). Some individuals and attributes may have no lines, while others may have many lines:
Persuasive in subtle, hidden, unspoken ways
Manage to occupy many different worlds and subcultures and niches
Information specialists
Most people fall into this category
Price vigilantes
Accumulate knowledge
Extraordinary knack of making friends and acquaintances
Like to initiate discussions with consumers, distribute coupons
Masters of the weak tie
Score very high on the Affective Communication Test
Information brokers, trading and sharing what they know
Can infect other people with their emotions
Connectors
Mavens
Salesmen
Persuasive in subtle, hidden, unspoken ways (S)
Manage to occupy many different worlds and subcultures and niches (C)
Information specialists (M)
Most people fall into this category (NONE)
Price vigilantes (M)
Accumulate knowledge (M)
Extraordinary knack of making friends and acquaintances (C)
Like to initiate discussions with consumers, distribute coupons (M)
Masters of the weak tie (C)
Score very high on the Affective Communication Test (S)
Information brokers, trading and sharing what they know (M)
Can infect other people with their emotions (S)
15 points to start
-1 point for each missing line
-1 point for each extra line
Consider this graph that represents a miniature World Wide Web, with vertices representing pages and edges representing hyperlinks:
- Which node will have the highest PageRank?
- Add a node (g) that has two links, one leading to (c) and one leading to (a). Will the PageRank of node (g) be HIGHER than, LOWER than, or the SAME AS (b)?
- Does adding the node (g) INCREASE, DECREASE or NOT AFFECT the rank of node (f)?
- After (g) is added, how many directed cycles does the graph have?
1. f
2. LOWER
3. INCREASE
4. 0
3 points for each. For 1, 1 point was awarded for "b," which is the node with second highest page rank.
In this question, we describe the launch of Pennster, a hypothetical online social network much like the Friendster and Orkut systems discussed in class. We ask questions about what the network is like at different steps. In this system, people are nodes and the mutual relationship of "Penn-friendship" is the only kind of link. Accepting an invitation to join Pennster is one way to create a "Penn-friendship" link between yourself and the person who invited you. Once on the system, you can offer Penn-friendship to another person who is already on Pennster. Accepting an offer of Penn-friendship (when both parties are already on the system) is the only other way to add a link of Penn-friendship. A person can unilaterally "un-Penn-friend" any Penn-friend, which removes the link that connects them.
- Kilian launches Pennster and is the only Penn-friend on the system.
- Kilian invites Michael and Nick.
- Nick accepts the invitation from Kilian.
- Michael accepts the invitation from Kilian.
- Michael invites Duncan to join Pennster.
- Nick invites Malcolm to join Pennster.
- Malcolm accepts the invitation from Nick.
- Kilian and Nick get into an argument and Nick un-Penn-friends Kilian.
- Malcolm offers Penn-Frienship to Michael.
- Michael accepts the offer from Malcolm.
- Kilian invites Thomas.
- Thomas accepts the invitation from Kilian.
- Duncan accepts the offer from Michael.
- Malcolm accuses Michael of misreading his book and un-Penn-friends him.
The following questions refer to Pennster and the sequence of 14 events listed above.
- If the Pennster graph is disconnected at any point, write the number of each step in which the graph becomes disconnected. If it is always connected, write "ALWAYS CONNECTED."
- Write Kilian's degree after each of the 14 steps above. Your answer will be a sequence of 14 numbers.
- After the last step, 14, consider all paths of finite length. Pick the shortest path between each pair of nodes. What is the maximum shortest path (the maximum number of links that must be traversed to get between any pair of nodes)? Write all of the people who lie along the path in order (including the people on the ends of it).
1. Either 8,14 (if you assume invitees are not part of the graph) or 2,5,14 (otherwise)
2. 0 0 1 2 2 2 2 1 1 1 1 2 2 2
3. Thomas-Kilian-Michael-Duncan (or the reverse)
6 points for each correct answer. An answer to 1 that is off by one from one of the acceptable sequences (e.g., "8" or "8,9,14") gets 1 point.
For each of the following graph generation models, write which of the following attributes the model has, in expectation: HEAVY-TAILED degree distribution, SMALL DIAMETER, and high CLUSTERING. (You can just write "HEAVY-TAILED," "SMALL DIAMETER," and/or "CLUSTERING" as is appropriate.) If the model has more than one attribute, write all of the appropriate terms. If the model has none of the attributes, write "NONE."
- Erdos-Renyi model
- Preferential attachment
- Duncan Watts' alpha model with alpha=6
- Jon Kleinberg's model with radius r=2
- Connect nodes 1 through 10 in a clique, then draw an edge from 10 to 11; then connect nodes 11 though 20 in a clique, then draw an edge from 20 to 21; and continue the process for each additional 10 nodes.
1. SMALL DIAMETER
2. HEAVY TAILED, SMALL DIAMETER
3. SMALL DIAMETER, CLUSTERING
4. No points were subtracted for this one
E. CLUSTERING
10 points to start
-1 for each missing attribute
-1 for each extra attribute
Down to a minimum of 0
Consider building a graph incrementally in this particular way: Begin with a graph that has two vertices and a single edge between them. At each step, add exactly two edges from a new vertex to two different nodes in the existing graph, selected uniformly at random. Note that this is a model for generating graph of the usual sort, with no self-loops or multiple edges between the same pair of vertices.
Consider graphs built from this model after 25 steps.
- How many vertices are in such graphs?
- How many edges?
- What is the minimum degree of vertices in such graphs?
- In expectation (that is, on average), which vertex will have higher degree, the vertex added at step 5 or the one added at step 17?
1. 27
2. 50+1=51
C. 2
D. 5
3 points for each. If "25" is given as an answer to 1 and "49" for 2 (incorrect base case), only 2 points are taken off rather than 6.
This question refers to the following figure, taken from the assigned readings.
Whose work is this figure taken from? Explain what "C," "L," and "α" are, noting which of them (if any) are free parameters of a model and which of them describe properties of a graph. In a sentence, answer this question: why is the shaded region of interest?
Duncan Watts. C is clustering (the property that neighbors are more likely to be connected than other random vertices); L is the graph property average path length, also called diameter; and α is a free parameter of the α-model that can vary between 0 and ∞. The shaded region is interesting because many networks observed in the world, from transportation to biological to social domains, have both high clustering and low diameter, which is seen in this region.
2 points for naming Watts
2 points for naming C as "clustering"
2 points for identifying C as a property
2 points for naming L as "average path length" or "diameter"
2 points for identifying L as a property
2 points for naming α as a free parameter
3 points for writing a sentence about the shaded region that is sensible
1 point for actually explaining why it is of interest: because interesting real-world networks have these properties
For each of the following, indicate whether the item describes
- a MODEL or technique for generating entire graphs,
- a mathematical PROPERTY of entire graphs, or
- NEITHER.
(Write either MODEL, PROPERTY, or NEITHER next to each item.) Note that we have only included models and properties that were discussed in lecture or in the readings; there are no obscure models and properties put here to trap you.
- G(N,p)
- Small diameter
- Context
- Chromatic number
- The PageRank algorithm
- Preferential attachment
- Heavy-tailed distribution of degree
- Bag of words
- Connected
- Acyclic
- Bacon number
- Tree
1. MODEL
2. PROPERTY
3. NEITHER
4. PROPERTY
5. NEITHER
6. MODEL
7. PROPERTY
8. NEITHER
9. PROPERTY
10. PROPERTY
12. NEITHER
12. PROPERTY
1 point if the only word written next to the item is the correct word
0 otherwise