SocialNetworks Flashcards
(31 cards)
What are the two critical questions that network structure helps answer in DAI?
- How long for entities to share information 2. How long to agree on a decision
What is the main reasons technological networks resemble on social networks?
Network formation is driven by underlying social network structure (similar laws)
What was the methodology of Milgram’s experiment (1967)?
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
What were the results of Milgram’s experiment?
42 out of 160 letters reached destination with average path length of 6 steps
What is the current average degree of separation on Facebook?
Around 4
What are three examples of Small World networks?
Hollywood, Web topology, and network of airlines
What are the four components of a graph G?
- Vertex set V(G) 2. Edge list E(G) 3. Size n (vertices) 4. Density M (edges)
What is the formula for average degree k in a graph?
M = nk/2
What is Distance D(i,j) in network measures?
Shortest path length between nodes i and j
What is Characteristic Path Length L(G)?
Mean of shortest path lengths (average “degree of separation”)
What is the neighborhood Γ(v) of a vertex?
Subgraph consisting of all vertices adjacent to v, excluding v
What is the neighborhood Γ(S) of a subgraph S?
Subgraph consisting of all vertices adjacent to any vertices of S, excluding S
What does the clustering coefficient measure?
The extent to which vertices adjacent to j are also adjacent to each other
What characterizes D-Lattice Networks?
Regular d-dimensional k-regular grids with good clustering but not small world properties
What are the three main properties of Random Networks?
- Low clustering 2. Short characteristic path length 3. Small world behavior
Why aren’t random networks good models of social networks?
They aren’t clustered at all, despite achieving small degrees of separation
What is the key principle of Watts-Strogatz Model?
Networks must be regular enough for clustering but chaotic enough for small degrees of separation
How is Watts-Strogatz Model created?
By rewiring regular lattice networks to preserve clustering while introducing shortcuts
What is Percolation in networks?
The process of propagation across a medium/network
What is Percolation threshold?
The critical value at which diffusion process can complete across the network
What does scale-free mean in networks?
Network properties are preserved independently of the scale at which we observe it
What is the power law formula for network connectivity?
P(k) = αk^(-γ)
What is the 20%-80% Rule in networks?
20% of system population consumes 80% of system’s resources
What are the two roles of important nodes in scale-free networks?
- Hubs: points most other nodes connect to 2. Connectors: nodes that connect large portions of network
