Evolution of Disconnected Components in Social Networks: Patterns and A Generative Model
Journal
2012 IEEE 31st International Performance Computing and Communications Conference, IPCCC 2012
Pages
305-313
Date Issued
2012-12
Author(s)
Abstract
The majority of previous studies have focused on the analyses of an entire graph (network) or the giant connected component in a graph. Here we study the disconnected components (non-giant connected components) in real social networks, and reporting some interesting discoveries on how these disconnected components evolve over time. We study six diverse, real networks (citation networks, online social networks, academic collaboration networks, and others), and make the following major contributions: (a) we make empirical observations of the longevity distribution of disconnected components, and find that the curve of the distribution demonstrates a decaying trend; (b) we find that the distributions of final size of disconnected components that merge with one another or get absorbed by the giant connected component both follow power laws; (c) we find that the majority of mergings are between disconnected components and the giant connected component. The mergings that happen among disconnected components are small in scale (involve only a few components). The longevity distributions of the disconnected components in those mergings are similar, where the shortest-lived disconnected components are the most in number; and (d) we propose an empirical generative model that can produce the networks with our observed patterns. © 2012 IEEE.
Subjects
disconnected components; evolution; generative models; giant connected components
Other Subjects
Citation networks; Collaboration network; Connected component; disconnected components; evolution; Generative model; On-line social networks; Power-law; Real networks; Social Networks; Merging; Social networking (online)
Type
conference paper