EE6605
HW#1 Solutions 2020
1-1
Path Lengths
Node
0
1
2
3
4
5
0
2
1
1
2
1
1
1
2
2
1
2
1
2
2
3
1
2
4
1
5
𝐿 = 2 6(6 − 1)
𝐷=2
(7 + 6 + 5 + 3 + 1) = 22 15
𝐶(0) = 1,𝐶(1) = 0,𝐶(2) = 1,𝐶(3) = 1,𝐶(4) = 0,𝐶(5) = 0 333
So, 𝐶 = 1 (1 + 0 + 1 + 1 + 0 + 0) = 1 63336
𝑘0 =3,𝑘1 =2,𝑘2 =3,𝑘3 =3,𝑘4 =2,𝑘5 =3 So, 〈𝑘〉=1(3+2+3+3+2+3)=8 63
All nodes have core value (= coreness) 2; the graph has coreness 2.
𝐵(0) = 0 + (5,0,3) + (5,0,2) + 0 (5,4) (5,4,3) + (5,0,3) (5,0,2) + (5,1,2) (5,1)
After normalization: 𝐵(0) = 1 = 1 (6−1)(6−2)/2 10
+ 0 + ⋯ + 0 = 1 + 1 = 1 2 2
𝐵(𝐸05) = (5,0,3) (5,4,3) + (5,0,3)
+ (5,0,2) + (4,5,0) (5,0,2) + (5,1,2) (4,3,0) + (4,5,0)
+
(1,5,0) (1,5,0) + (1,2,0)
+ 0 + ⋯ + 0
=1+1+1+1=2 2222
After normalization: 𝐵(𝐸 ) = 2 = 1 05 6(6−1)−1 7
2
Core value (= coreness) of every node = 2; coreness of the network = 2 1-2 (Answers are not unique, as long as they make sense)
Structure
Advantage
Disadvantage
Fully-connected
efficient, robust
costly, redundant
Meshed
efficient, uncostly
irregular (difficult to manage)
Star
centralized
fragile to attacks
Bus
point to point
main path needs high bandwidth
Ring
data have two directions to go
inefficient (data always go through many unrelated nodes)
EE6605 HW#1 Solutions 2020
1-3 (There are many examples, up to the student to choose and show)
(i) Random-graph network
(ii) Small-world network
(iii) Scale-free network
(iv) Weak-tie phenomenon
(v) 80-20 rule
(vi) 90-9-1 rule