View source for Statistical properties of community structure in large social and information networks. In WWW ’08

From Cohen Courses

← Statistical properties of community structure in large social and information networks. In WWW ’08

You do not have permission to edit this page, for the following reason:

---

You can view and copy the source of this page.

Statistical properties of community structure in large social and information networks. In WWW ’08 == Citation == Leskovec, Jure, et al. "Statistical properties of community structure in large social and information networks." Proceeding of the 17th international conference on World Wide Web. ACM, 2008. == Online version == [http://cs-www.cs.yale.edu/homes/mmahoney/pubs/Communities_WWW.pdf PDF] == Summary == This [[Category::Paper]] discusses some statistical properties and observed facts of [[AddressesProblem::community structure]] when using network community profile (NCP) plot, which measures the quality of "best" community (they use conductance to measure the quality) as a function of community size. The main empirical findings are as following: * There exists a specific size, which empirically is roughly 100 nodes, for the global "best" community. And before this size, there exist well-separated communities (called Whiskers by the author) and they often can be combined well into meaningful larger communities. However, after this size, the best possible communities become more and more "blended into" the remainder of the network and less and less community-like. * This specific "best" size for meaningful communities seems irrelevant with network size. And their observed properties are not reproduced, at even a qualitative level, by any of the commonly-used network generation models they have examined, including preferential attachment, copying, and hierarchical network models. == Network Community Profile plot == [[UsesMethod::Network Community Profile]] (NCP) plot is the key idea of this paper. It tries to measure the quality of best community as a function of community size. If we use [[UsesMethod::Conductance]] to measure the quality of communities, NCP is defined as <math>\Phi(k)=\min_{S\subset V, |S|=k}{\phi(S)}</math>. As smaller conductance means better community, NCP plot over real world communities often have a 'V' shape which shows the existence of a specific "best" community size and it is roughly 100 empirically. == Conductance == The [[UsesMethod::Conductance]] of a cut <math>(S, \bar S)</math> in a graph is defined as: :<math>\varphi(S) = \frac{\sum_{i \in S, j \in \bar S}a_{ij}}{\min(a(S),a(\bar S))}</math> where the <math>a_{ij}</math> are the entries of the adjacency matrix for ''G'', so that :<math>a(S) = \sum_{i \in S} \sum_{j \in V} a_{ij}</math> is the total number (or weight) of the edges incident with ''S''. == Generative Models for network community structure == The observation from NCP can be tested on network generative models by checking if the model can reproduce the phenomena from NCP. The author found that many commonly-used network models cannot reproduce the phenomena. Either they cannot generate small communities which can be combined well or they generate a network in which larger communities can have better qualities. And they suggest a so-called [[UsesMethod::Forest Fire Model]] can captures some of the phenomena and they give some empirical result of generating networks. == Coherence with ground truth communities == The paper modified NCP by considering only ground truth communities from the datasets. And they found that the V shape still hold in ground truth communities. == Datasets == *Social networks **[[UsesDataset::LiveJournal]] **[[UsesDataset::Epinions]] **[[UsesDataset::CA-DBLP]] *Information networks **[[UsesDataset::CIT-HEP-TH]] **[[UsesDataset::AmazonProd]] *Web graphs **[[UsesDataset::Web-GOOGLE]] **[[UsesDataset::Web-WT10G]] *Bipartite affiliation networks **[[UsesDataset::ATP-DBLP]] **[[UsesDataset::ATM-IMDB]] *Internet networks **[[UsesDataset::AsSkitter]] **[[UsesDataset::GNUTELLA]] ==Study plan== *[[Conductance]] is the central way in this paper: ** [http://en.wikipedia.org/wiki/Conductance_(graph) conductance in Wikipedia] ** [[Kannan, et al. "On clusterings: Good, bad and spectral". J. ACM 2004]] ==Related work== *[[FRK Chung and L.Lu. Complex Graphs and Networks, AMS 2006]] *[[J. Leshovec et al Graphs over time: densification laws, shrinking diameters and possible eplanations. KDD 05]]

Return to Statistical properties of community structure in large social and information networks. In WWW ’08.