Information Pathways in Social Networks

The first talk presented in the social network session of KDD 2008 was for an interesting paper by G. Kossinets, J. Kleinberg, and D. Watts titled The Structure of Information Pathways in a Social Communication Network (PDF). Although I was not at KDD I was able to watch it online at videolectures.net.
Kleinberg, the presenter, made some interesting observations having to do with our "rhythmic" everyday conversations. The approach to analyzing communication within these social networks is focused on the frequency of correspondence, rather than the content conveyed.

They measure "distance" between individuals by measuring the minimum time required for information to pass from one node to another. A methodology based on Lamport's work and vector clocks in the area of distributed computing.

Using this metric they are able to filter a busy network (one having edges for all communication packets) in a simplified network that contains only the edges that are minimum-delay paths between a pair of nodes. They call this simplified network view the network backbone. Below is an example of such a network (along with the caption) taken from the paper.
The nodes further outside of the center of the graph are more "out-of-date" with respect to node v, since they communicate less frequently.

I found the approach to be novel and useful. As with nearly any analysis technique, caution should be used in selecting the time-period and group size to be studied. Recency and frequency issues come into play as correspondence is aggregated. However, this pursuit offers another approach for more fully understanding information flow.

DML Research Collaboration

In effort to collaborate and refine our research at a faster pace, it might be fun to (1) blog about our research ideas each week and then (2) visit each lab member's blog to comment on what they have written to encourage good ideas and weed out the bad.

What do you think?

Weekly Update

The tasks that I was involved (and some thoughts) during this week include the following:

Outlined a preliminary schedule and brainstormed for the "Making a Blog Big" project with Nathan Purser

Read more about Structural Holes and Network Closure, including:

• Ronald Burt's Structural Holes versus Network Closure (PDF). Notes:
  
• Some more quickly become prominent; some enjoy higher incomes; some lead more important projects; the interests of some are better served than interests of others. Better connected people enjoy higher returns. (These are some things that we could use to validate our social capital metrics.)
  
• The Social Capital Metaphor is "people that are better connected do better", whereas the Human Capital Metaphor is "people who do better are more able individuals; they are more intelligent; more attractive; more articulate; more skilled."
• A generic research finding in sociology and social psychology is that information circulates more within than between groups
• Social capital can be argued to exist in structural holes (bridging) and network closures (bonding). However, the studies he performs and shows indicate that structural holes are the source of social capital.
• Networks of densely interconnected contacts are systematically associated with substandard performance (bonding); networks that span structural holes are associated with creativity and innovation, positive evaluations, early promotions, high compensation and profits (bridging).
• There remains an important role for closure. It can be critical to realizing the value buried in structural holes.
• The mechanisms remain distinct. Closure describes how dense or hierarchical networks lower the risk associated with transaction and trust, which can be associated with performance. The hole argument describes how structural holes are opportunities to add value with brokerage across the holes, which is associated with performance.
  
• Bruce Hoppe's blog post, Reputation and Trust (aka "Network Closure")
• Uses a good personal example of Network Closure
  
• I commented, "Virtual communities, no doubt, have an impact on real communities. However, I would argue that Putnam's work stands as does Burt's. The main issue seems to be that social capital is challenging to define precisely. Are there any agreed upon mathematical definitions of social capital? (It seems that there is still too much ambiguity.)"

Reading that I like to get to:

• Nan Lin's Building a Network Theory of Social Capital (PDF)
• Unpacking Burt's Redundancy Measure
• Measurement of Social Capital
  

Found some other interesting resources, along the way:

• Institute for Social Network Analysis of the Economy (ISNAE)
  
• Social Network Researchers By Author (at ISNAE)
  
• Introduction to Networks Mathematics by Bruce Hoppe
  
• Bruce Hoppe's blog
• Social Network Researchers:
• Wayne Baker
• Steve Borgatti
• Ron Burt
• Rob Cross
• Jonathon Cummings
• Jon Kleinberg
• David Krackhardt
• Valdis Krebs

Finding an Important Problem

There seems to be infinitely many problems in the world. The trick is finding one that is sufficiently interesting to focus a dissertation on. The hope is that it has the following qualities:

• Should impact a diverse audience (more than just the geeks in the computer lab)
• Should be scientific yet have a host of business applications
  
• Would be nice if it were related, at least in part, to my previous work
• To be continued...

Generating Research

As I am amidst the decision of what to focus my PhD work on, my thoughts take me back to a talk given nearly a year ago by Dan Olsen. In this presentation he mentioned the following steps for generating research:

1. Find an important problem
2. Generate lots of ideas
3. Filter them down
4. Make them real

This week I'd like to work on the step 1 and find an important problem in the realm of data mining and likely social networks. I'll let you know what I come up with.

Let It Live

This is a little presentation that I gave to the DML today.