Actions

Difference between revisions of "Networks Basic Statistics"

From OPOSSEM

(Clustering Coefficient)
(Clustering Coefficient)
Line 28: Line 28:
  
 
=Clustering Coefficient=
 
=Clustering Coefficient=
 +
Consider, for a moment, two different ways your own personal friend circle could look.  Assuming that you have <math>N</math> friends in your circle, on one extreme, all of your friends could know one another.  On the other extreme none of your friends know one another.  From a network perspective the former situation would have all your friends connected to each other by edges; in the latter situation you would be like a hub, connected to each friend by and edge, but none of those friends being connected to one another.  When all an individual's friends (more generally when a node's neighbors) are connected to one another, we call that part of the network highly ''clustered''.
 +
 +
Clustering can have very serious implications in social systems.  Consider how different your birthday party would be if all your friends knew one another versus if nobody knew each other.  In the latter situation, it would be hard to even get people to come due to a complete lack of social cohesion!  This playful example is no different from clustering in more serious situations involving political actors.  A well connected neighborhood creates a basis for social and political action, a pillar of political science.  For this reason, being able to detect and quantify the degree of clustering in a network is a useful tool and can offer profound insights into the behavior we might expect from a social system.
  
 
==Global Clustering Coefficient==
 
==Global Clustering Coefficient==
  
 
==Local Clustering Coefficient==
 
==Local Clustering Coefficient==
 +
 +
[[File:Clustering_coefficient_example.png]]
  
 
==Network Average Clustering Coefficient==
 
==Network Average Clustering Coefficient==

Revision as of 06:56, 8 July 2011


Objectives

  • Compute the degree distribution for undirected and directed networks
  • Quantify the local density of connectivity in the network
  • Understand why motif distributions must be estimated in large networks

Introduction

Fundamentally, a network is a body of data. As with other data sets, our first task it to identify significant features of that data. In much the same way as the mean and standard deviation are easy to compute but very valuable summary statistics, degree, clustering, and motif statistics are easy to compute attributes that can reveal a great deal about the structure of a network. We discuss these different basic statistics here.

Degree-based Statistics

Given that networks are composed of nodes with relationships, an obvious first question to ask is how these relationships are distributed among the nodes in the network. The number of edges that are incident to a node is called the node's degree. In this section we discuss some ways in which the degree of nodes can help us understand the structure of the network and the mechanisms that formed it.

Degree Density

A very easy-to-compute attribute we can consider is the average degree of nodes in the network: how many edges does each node have? This can be calculated using the ratio <math>\frac{2|E|}{|V|}</math> which indicates the number of edges on average that are incident to a node.

Degree Distribution

The problem with using average degree is that, as with all statistical distributions, it can be produced by a wide array of distributions. In fact, the distribution of edges can tell us much more than just the average about the distribution of power and resources within the network. Consider, as an example, the campaign contribution network discussed earlier. A network in which all candidates have similar number of contributions (edges) would indicate a very different world from a network in which most contributions (edges) go to a handful of candidates with most receiving very few. Both could have the same average degree, but the former network would indicate that resources are fairly distributed among candidates; the latter would suggest that a handful of candidate receive a disproportionate number of resources. Determining what situation exists in the real world would help us in formulating hypotheses about how the campaign system works.

In order to study this distribution, we could look at the degree distribution. The degree distribution, <math>P(k)</math> is the fraction of nodes with degree <math>k</math>. Often the cumulative degree distribution is also considered, which is the fraction of nodes with degree less than or equal to <math>k</math>.

In and Out Degrees

In directed networks, where edges point from one node to another, there are two distributions: the in-degree <math>P^+(k)</math> which is the fraction of nodes with in-degree of <math>k</math> and the out-degree <math>P^-(k)</math> which is the fraction of nodes with out-degree of <math>k</math>.

Scale-free Distributions

One distribution which has been observed in a wide array of networks is called the scale-free distribution. This distribution follows a power-law, <math>P(k) \approx k^{-\gamma}</math>. On a qualitative level, in a network with such a distribution, the majority of the nodes have very low degree, but with a small, but non-trivial number of nodes have very high degree. The high degree nodes are called 'hubs' and are often found to hold positions of power in the network proportional to their degree.

Clustering Coefficient

Consider, for a moment, two different ways your own personal friend circle could look. Assuming that you have <math>N</math> friends in your circle, on one extreme, all of your friends could know one another. On the other extreme none of your friends know one another. From a network perspective the former situation would have all your friends connected to each other by edges; in the latter situation you would be like a hub, connected to each friend by and edge, but none of those friends being connected to one another. When all an individual's friends (more generally when a node's neighbors) are connected to one another, we call that part of the network highly clustered.

Clustering can have very serious implications in social systems. Consider how different your birthday party would be if all your friends knew one another versus if nobody knew each other. In the latter situation, it would be hard to even get people to come due to a complete lack of social cohesion! This playful example is no different from clustering in more serious situations involving political actors. A well connected neighborhood creates a basis for social and political action, a pillar of political science. For this reason, being able to detect and quantify the degree of clustering in a network is a useful tool and can offer profound insights into the behavior we might expect from a social system.

Global Clustering Coefficient

Local Clustering Coefficient

Error creating thumbnail: Unable to save thumbnail to destination

Network Average Clustering Coefficient

Motif Distributions

Conclusion

References

<references group=""></references>

Discussion questions

Problems

Glossary

  • [[Def: ]]
  • [[Def: ]]
  • [[Def: ]]