P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-06 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:15
6.2 Community Evolution 163Figure 6.11. Network Segmentation. The network is decomposed into a giant component
(dark gray), star components (medium gray), and singletons (light gray).- Singletons: These are orphan nodes disconnected from all nodes in
the network.
Figure6.11depicts a segmented network and these three components.Graph Densification
It is observed in evolving graphs that the density of the graph increases as
the network grows. In other words, the number of edges increases faster
than the number of nodes. This phenomenon is calleddensification. Let
V(t) denote nodes at timetand letE(t) denote edges at timet,|E(t)|∝|V(t)|α. (6.26)If densification happens, then we have 1≤α≤2. There is linear growth
whenα=1, and we get clique structures whenα=2 (why?). Networks
exhibitαvalues between 1 and 2 when evolving. Figure6.12depicts a
log-log graph for densification for a physics citation network and a patent
citation network. During the evolution process in both networks, the number
of edges is recorded as the number of nodes grows. These recordings show
that both networks haveα≈ 1 .6 (i.e., the log-log graph of|E|with respect
to|V|is a straight line with slope 1.6). This value also implies that when
V is given, to realistically model a social network, we should generate
O(|V|^1.^6 ) edges.