Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computing and Information Science
  4. Computing and Information Science Technical Reports
  5. Detecting the Structure of Social Networks using (\alpha, \beta)-Communities

Detecting the Structure of Social Networks using (\alpha, \beta)-Communities

File(s)
WAW2011.pdf (266.94 KB)
Permanent Link(s)
https://hdl.handle.net/1813/22415
Collections
Computing and Information Science Technical Reports
Author
He, Jing
Hopcroft, John
Liang, Hongyu
Suwajanakorn, Supasorn
Wang, Liaoruo
Abstract

An (\alpha,\beta)-community is a subset of vertices C with each vertex in C connected to at least \beta vertices of C (self-loops counted) and each vertex outside of C connected to at most \alpha vertices of C (\alpha<\beta). In this paper, we present a heuristic (\alpha,\beta)-Community algorithm, which in practice successfully finds (\alpha,\beta)-communities of a given size. The structure of (\alpha,\beta)-communities in several large-scale social graphs is explored, and a surprising core structure is discovered by taking the intersection of a group of massively overlapping (\alpha,\beta)-communities. For large community size k, the (\alpha,\beta)-communities are well clustered into a small number of disjoint cores, and there are no isolated (\alpha,\beta)-communities scattered between these densely-clustered cores. The (\alpha,\beta)-communities from the same group have significant overlap among them, and those from distinct groups have extremely small pairwise resemblance. The number of cores decreases as k increases, and there are no bridges of intermediate (\alpha,\beta)-communities connecting one core to another. The cores obtained for a smaller k either disappear or merge into the cores obtained for a larger $k$. Further, similar experiments on random graph models demonstrate that the core structure displayed in various social graphs is due to the underlying social structure of these real-world networks, rather than due to high-degree vertices or a particular degree distribution.

Sponsorship
This research was partially supported by the U.S. Air Force Office of Scientific Research under Grant FA9550-09-1-0675, the National Natural Science Foundation of China under Grant 60553001, and the National Basic Research Program of China under Grant 2007CB807900 and 2007CB807901.
Date Issued
2011-03-22
Keywords
community structure
•
social networks
•
(\alpha,\beta)-community
•
core structure
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance