Proceedings of a Workshop on Statistics on Networks (CD-ROM) (2007) / Chapter Skim
Currently Skimming:
Mixing Patterns and Community Structure in Networks--Mark Newman, University of Michigan and Santa Fe Institute
Mixing Patterns and Community Structure in Networks--Mark Newman, University of Michigan and Santa Fe Institute
Pages 74-119
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 74... ...
I will assume that you know what a social network is. It is a network where the nodes are, for example, people and they are connected together by some social interaction such as they're friends, or they have business acquaintanceships, or they have been in close physical proximity recently.
|
From page 75... ...
In the kinds of problems you want to solve in computer science, often you are just given the network and you want to find whatever the best division of it is into groups, such that you have a bunch of these tightly knit groups, and there are lots of connections within the groups, and only a few connections between the groups, and you do the best you can with whatever network you are given. We are taking a slightly different point of view here, and assuming from the outset that there is some good division for some good sociological reason, for example, that your social network naturally divides up into these groups, and we would like to find the natural divisions of the network.
|
From page 76... ...
you want beforehand, because when you swap two vertices, you don't change the size of the groups. Each group gets one vertex and loses one vertex.
|
From page 77... ...
FIGURE 4 If you have a network that is approximately block diagonal, that is precisely the sort of 77
|
From page 78... ...
You just find -- if your matrix really is approximately block diagonal with two blocks -- what those blocks are. But this algorithm only bisects, and it is a rather slow algorithm, since it involves finding the leading eigenvectors of the matrix.
|
From page 79... ...
In fact, if I lived anywhere within my dotted circle and I wanted to drive anywhere within another circle, I am going to end up going over that bridge. If you live in San Francisco and you want to get to the East Bay, you would go over the Bay Bridge, and that is the way you have to go.
|
From page 80... ...
The vertices represent students in this club who were practicing their karate, and connections between them represent friendships as determined by direct observation of the members of the club by a sociologist who was working with them. This is an interesting example.
|
From page 81... ...
In a way, this is a silly example but we look at examples like this for a good reason, which is they are cases where we think we know what the answers should be. You want to have applications to real world networks to show that this really is working, but you also want, when you are developing algorithms, to apply it to something where you can tell, after you did it, whether it is actually giving a sensible answer.
|
From page 82... ...
In this case this is a food web, a non-social network example, a food web of marine organisms in the Chesapeake Bay. The interesting thing about what happens when we feed this one into the algorithm is that it appears to split the food web into the pelagic organisms, the ones that live in the upper layers of the water, and the benthic ones, the ones that live in the mud down at the bottom.
|
From page 83... ...
What we use instead is the fraction of edges that fall within the groups minus the expected fraction of edges that would fall within those groups. I can write down exactly how we calculate that if you like, but the basic idea you can see by examining that trivial partition.
|
From page 84... ...
We usually find that there is something significant going on if it is anywhere above about 30 percent, and the highest values we have seen in real networks are about 80 percent. FIGURE 10 Figure 11 shows what happens if you apply this method to the karate club network.
|
From page 85... ...
FIGURE 11 Once you have this modularity, it allows you to say what the division of a network into groups is. Now I can draw a picture like Figure 12, where I have taken a network and have colored the groups by whatever corresponds to this maximum modularity.
|
From page 86... ...
, pretty much correspond to known groups of collaborators at known institutions. Taking it one step further, you can take this and make this meta network shown in (c)
|
From page 87... ...
represent the number of people and the number of collaborations. I think that this is the sort of thing that could be very useful for analyzing these very large network data sets that we are getting now.
|
From page 88... ...
National Longitudinal Study of Adolescent Health, the AdHealth study. Jim Moody, who is here, is heavily involved in this.
|
From page 89... ...
Remember, degree is how many connections you have. In social networks, the gregarious people are hanging out with the gregarious people, and for all the other kinds of networks, at least the ones I have looked at, you have disassortative mixing, where the high-degree nodes are connected to the low-degree nodes.
|
From page 90... ...
What it is representing basically is that disease spreads more easily if the network is assortative than if it is disassortative, and sadly, we find that most social networks are assortative. So, that could be a bad thing.
|
From page 91... ...
Rather, you should be targeting school children or people who have many contacts. Not only can you protect them, but they are likely to spread it to other people and you can protect the people they would spread it on to.
|
From page 92... ...
Again, unfortunately, the assortative case, which is common in real social networks, is much more robust to the removal of these vertices. The hand-waving explanation for that is they are all clumped together in this big clump in the middle, and you are removing a lot of people from the same spot, all in the middle of the network, and you are leaving the rest of the network untouched.
|
From page 93... ...
Just because you are in a group together doesn't mean you know everybody in that group, so only some fraction of the edges are present here. This makes a simple model of what I showed on Figure 20, and this is actually something that we know how to do mathematically -- take a bipartite graph, do a one-mode projection onto just one half of the bipartite graph, and then take out some fraction of the edges.
|
From page 94... ...
DR. HANDCOCK: Obviously, looking at clustering as a canonical problem in social networks, my question is, how does your method compare to other algorithmic methods such as block modeling, generalized block modeling, and also model-based methods such as Nowicki and Snijders's method.
|
From page 95... ...
However, there are, of course, other very simple methods that have been proposed by sociologists that work well, like standard hierarchical clustering method, you have to propose some measure of similarity between vertices before you can do the hierarchical clustering of them, and of course, other very simple methods that have been proposed by sociologists that work well, like standard hierarchical clustering methods. I think those have many of the same advantages as ours does, but they work in very different ways.
|
From page 96... ...
1995. "Data Driven Network Models for the Spread of Infections Disease." Epidemic Models: Their Structure and Relation to Data.
|
From page 97... ...
FIGURE 1 In social network analysis the row labels are the same as the column labels, where we are measuring relationships between these nodes. I am going to use the old workhorse of multivariate analysis, the singular value decomposition, to analyze these types of data.
|
From page 98... ...
You might say, binary data: I am going to fit a logistic regression relating these explanatory variables to my network observations. You model the log odds of there being a tie between two nodes as βTxi,j.
|
From page 99... ...
Figure 3 shows a network and how within-node homogeneity or across-node heterogeneity might be manifested in this network. One of the first things we might observe is that some of these nodes have just one ingoing or one outgoing tie, whereas some other nodes have many, many, many ties.
|
From page 100... ...
That's the obvious thing that a statistician would do as a first pass, but in network data there is just an additive structure on this log odd scale. There is probably a lot more going on, and we know this from studying the sociology of these social networks.
|
From page 101... ...
FIGURE 4 One such model is the sort of stochastic block structure or latent class model by Nowicki and Snijders, and this was the idea that was mentioned before, that maybe nodes belong to some class, and nodes form ties with people in the same class or category preferentially. This is shown in Figure 4.
|
From page 102... ...
Many of you are familiar with the singular value decomposition. It basically is just that any matrix has a decomposition into a set of what are called, say, left singular vectors, which I am denoting U, right singular 102
|
From page 103... ...
The interpretation here, again, is that for each of the rows we have latent row characteristics, for each of the columns we have latent column characteristics. The model says, let's try to represent the relationship between these nodes using these latent characteristics.
|
From page 104... ...
I didn't want to just do that decomposition. I need to incorporate the singular value decomposition in a statistical model, and I also want to figure out what the dimension is and what an appropriate dimension is.
|
From page 105... ...
Figure 8 says just a little bit about the prior distribution for U, and it is going to be the same as the prior distribution for V Remember, U is this vector of latent characteristics for the rows.
|
From page 106... ...
The posterior distribution is proportional to the prior distribution times the probability of the data given the jth column, as shown in Figure 9. This is just through the Gaussian model for Y
|
From page 107... ...
Also, we might think that we need more than one or two dimensions, so we would like to evaluate the dimension of the latent characteristics and select a model in a principled way. Basically, the problem reduces down to this problem shown in Figure 10.
|
From page 108... ...
I am now going to show how this might actually work in practice. For those of you who have taken some multivariate data and said, ah, I have genes on this thing on the rows and I have tumors on the columns, and I want to see the effects going on here, maybe you have looked at the singular value decomposition of your data to try to sort out what is going on in the data.
|
From page 109... ...
If you have played around with these things you know that you are looking for gaps in the magnitude from one singular value to the next. You know it is definitely more than zero.
|
From page 110... ...
I used the Bayesian machinery. You can get a posterior distribution for the mean matrix, and then you can look at the posterior mean of all the singular values.
|
From page 111... ...
If you take the true matrix that was used to generate the data, tab all those entries, and plot them against the least-squares estimate, you get the green pattern shown on the right side of Figure 14.
|
From page 112... ...
Data matrix Y is equal to the mean matrix plus error so the singular value decomposition is projecting all the error as well onto the subspace. It is probably best to point out that looking at the range of the truth is –3 to 3, and the range of the singular value decomposition is essentially –4 to 4.
|
From page 113... ...
In this context, you can fit binary data where you model the log odds of the observations as being equal to the structure. If you have count data you might model things on the log scale and, if it is continuous, you might model it on the additive scale, using the identity link.
|
From page 114... ...
We say that we are going to model the mean of each observation on the log scale with this regression part plus this latent structure. I was very happy to see the posterior distribution on the number of dimensions of the latent structure as shown in Figure 17.
|
From page 115... ...
There are lots of countries that are very active in conflict, and a lot of countries that are attacked a lot; you know that you are going to have row and column effects, and that is a 2-dimensional structure. Therefore, you know the dimension has got to be at least two.
|
From page 116... ...
All you would see is a bunch of green lines scattered all over the place like that so you can see how these positions really do pick up the structure that is there. To summarize, my point is that singular value decomposition is a well-known tool in multivariate analysis that has been used for a long time, and there is a huge literature based on it, sort of in the additive case in the psychometric literature in lots of fields.
|
From page 117... ...
One way is to have a time-series model for the latent characteristics, as a Markov model or something like that, and actually David Banks and Eric Vance are working on stuff like that. Again, I have some other ideas about how to set these things up in a general autoregressive structure.
|
From page 118... ...
There can be an advantage to leaving it out and then plotting it versus the latent characteristics later. You could do what I just said, try to -- the way I have the model set up, you can constrain the latent characteristics to be orthogonal to things, and you could actually restrict them to be orthogonal to sort of the design structure of the regression and say, yes, it is the left-over variation.
|
From page 119... ...
2002. "Latent Space Approaches to Social Network Analysis." Journal of the American Statistical Association (97)
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.