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 161- Recalculate betweenness for all edges affected by the edge removal.
- Repeat until all edges are removed.
Example 6.4.Consider the graph depicted in Figure6.9(a). For this graph,
the edge-betweenness values are as follows:
⎡
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢
⎣123 4 5 6 789
1 041 9 0 0 000
2 404 0 0 0 000
3 140 9 0 0 000
4 909 0 1010000
5 00010 0 1 630
6 00010 1 0 630
7 000 0 6 6 028
8 000 0 3 3 200
9 000 0 0 0 800
⎤
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
. (6.25)
Therefore, by following the algorithm, the first edge that needs to be
removed is e(4,5)(or e(4,6)). By removing e(4,5), we compute the edge
betweenness once again; this time, e(4,6)has the highest betweenness
value: 20. This is because all shortest paths between nodes{1,2,3,4}to
nodes{5,6,7,8,9}must pass e(4,6); therefore, it has betweenness 4 ×
5 = 20. By following the first few steps of the algorithm, the dendrogram
shown in Figure6.9(b) and three disconnected communities({ 1 , 2 , 3 , 4 },
{ 5 , 6 , 7 , 8 },{ 9 }) can be obtained.We discussed various community detection algorithms in this sec-
tion. Figure6.10summarizes the two categories of community detection
algorithms.6.2 Community Evolution
Community detection algorithms discussed so far assume that networks are
static; that is, their nodes and edges are fixed and do not change over time.
In reality, with the rapid growth of social media, networks and their internal
communities change over time. Earlier community detection algorithms
have needed to be extended to deal with evolving networks. Before analyz-
ing evolving networks, we need to answer the question,How do networks
evolve?In this section, we discuss how networks evolve in general and then