Thinking cap questions: Social networks..

Here are a couple of questions you can discuss (feel free to add other questions you want discussed too). You might want to look at the
blog to see other comments already made before you add your own. Also feel free to only answer the hard ones..

A. We considered three types of measures of centrality and prominence: based on degree, based on "closeness" to other entities in the network and
based on "between-ness"--i.e., how often is the entity going to be on the geo-desic path between other actor pairs. W.r.t. these, think of the following:

A0. Consider three canonical networks of size n: a star network, where one entity has (undirected) edges to all other entities; a circle network; and a line network.
Think of what are the most "important" nodes in each of the networks, if we measure importance by degree based, closeness-based and between-ness based
notions respectively.

A1. are all these measures equally applicable to both directed and undirected social networks?

A2. In the case of directed social networks, can you attach different notions of importance to in-degree and out-degree?

A3. Can you think of generalizing the in- and out- degree based notions to transitively take into account the importance of the actor from/to
which the edge is directed? (basically, you somehow want to say that the importance of a link from a node is proportional in some way to the
importance of the node itself).

A4. In the questions above, we kept silent about the label of the edge. Suppose in one network, the edges signify the relation "respects" and in
other network they signify the relation "hates". Does this difference throw a wrench into the kind of analysis the measures in 3 are trying to compute?

A5. Can you think of cases where closeness and between-ness measures of importance could be useful in the web-based networks (social networks, blogs or
page networks)?

B. We talked about small-world networks where the largest geo-desic path between any pair of
connected nodes in the network, also called the diameter of the network, is log of the size of the network.

B0: which of the networks in A0 are small-world networks by this definition?

B1: Suppose you are an actor in a small-world network of size N, and you only have local information (i.e., have access to only the links
incident on you). Suppose you are trying to look for a path to another actor/entity in the network with a certain "goal" property g().
We are interested in characterizing how much work you will need to do, in the worst case and the best case, to find this actor. Answer the
following:

B.1.1 What is the difference between this scenario and the usual graph-search problems you learned about in 310 or 471?

B.1.2. What is the best and worst case complexities (you decide how to measure complexity) of the task?

B.1.3. How does your answer to B.1.2. change if you have access to the whole network (i.e., you can see all the connections between all the nodes)

========that is all for now================