SocialNetworks

Question 1

What are the two critical questions that network structure helps answer in DAI?

Answer 1

1. How long for entities to share information 2. How long to agree on a decision

Question 2

What is the main reasons technological networks resemble on social networks?

Answer 2

Network formation is driven by underlying social network structure (similar laws)

Question 3

What was the methodology of Milgram’s experiment (1967)?

Answer 3

Letters were sent to random individuals who had to either send directly to target if known, or forward to an acquaintance more likely to know the target

Question 4

What were the results of Milgram’s experiment?

Answer 4

42 out of 160 letters reached destination with average path length of 6 steps

Question 5

What is the current average degree of separation on Facebook?

Answer 5

Around 4

Question 6

What are three examples of Small World networks?

Answer 6

Hollywood, Web topology, and network of airlines

Question 7

What are the four components of a graph G?

Answer 7

1. Vertex set V(G) 2. Edge list E(G) 3. Size n (vertices) 4. Density M (edges)

Question 8

What is the formula for average degree k in a graph?

Answer 8

M = nk/2

Question 9

What is Distance D(i,j) in network measures?

Answer 9

Shortest path length between nodes i and j

Question 10

What is Characteristic Path Length L(G)?

Answer 10

Mean of shortest path lengths (average “degree of separation”)

Question 11

What is the neighborhood Γ(v) of a vertex?

Answer 11

Subgraph consisting of all vertices adjacent to v, excluding v

Question 12

What is the neighborhood Γ(S) of a subgraph S?

Answer 12

Subgraph consisting of all vertices adjacent to any vertices of S, excluding S

Question 13

What does the clustering coefficient measure?

Answer 13

The extent to which vertices adjacent to j are also adjacent to each other

Question 14

What characterizes D-Lattice Networks?

Answer 14

Regular d-dimensional k-regular grids with good clustering but not small world properties

Question 15

What are the three main properties of Random Networks?

Answer 15

1. Low clustering 2. Short characteristic path length 3. Small world behavior

Question 16

Why aren’t random networks good models of social networks?

Answer 16

They aren’t clustered at all, despite achieving small degrees of separation

Question 17

What is the key principle of Watts-Strogatz Model?

Answer 17

Networks must be regular enough for clustering but chaotic enough for small degrees of separation

Question 18

How is Watts-Strogatz Model created?

Answer 18

By rewiring regular lattice networks to preserve clustering while introducing shortcuts

Question 19

What is Percolation in networks?

Answer 19

The process of propagation across a medium/network

Question 20

What is Percolation threshold?

Answer 20

The critical value at which diffusion process can complete across the network

Question 21

What does scale-free mean in networks?

Answer 21

Network properties are preserved independently of the scale at which we observe it

Question 22

What is the power law formula for network connectivity?

Answer 22

P(k) = αk^(-γ)

Question 23

What is the 20%-80% Rule in networks?

Answer 23

20% of system population consumes 80% of system’s resources

Question 24

What are the two roles of important nodes in scale-free networks?

Answer 24

1. Hubs: points most other nodes connect to 2. Connectors: nodes that connect large portions of network

Question 25

What are the two steps in Barabási-Albert Model?

Answer 25

1. Start with m0 initial nodes 2. Add new node each step with m edges linking to existing nodes

Question 26

What is the formula for attachment probability in BA Model?

Answer 26

∏(ki) = ki / ∑j kj

Question 27

Why are scale-free networks error tolerant?

Answer 27

Network structure maintains integrity and path lengths remain stable against random failures

Question 28

Why are scale-free networks vulnerable to attacks?

Answer 28

Targeted attacks on hubs fragment network quickly and increase path lengths dramatically

Question 29

What is the percolation threshold in scale-free networks?

Answer 29

Practically zero

Question 30

What are Communities in networks?

Answer 30

Sets of nodes highly interconnected with each other but less connected with others

Question 31

What is a Temporal Network?

Answer 31

A time-varying graph showing active links or links active during specific periods