Graphs Flashcards
What does it mean for a graph to be strongly connected?
A graph is strongly connected if there is a directed path from any node to any other node.
What is a clique?
A maximum strongly connected subgraph
What is an incidence matrix?
A VxE matrix containing edge data.
What is the diameter of a random graph?
The greatest distance between any two verticies.
What is the equation for average degree k in a random graph?
k = pN, where N is the number of nodes and p is the probability of any two nodes being connected.
What is the average path length in a random graph?
ln(N)/ln(k), where N is the number of nodes and k is the average degree.
How does the topology of a random graph vary for different values of k?
k small, isolated clusters, short path lengths.
k=1 => a giant component appears, path lenghts are high.
k>1 => almost all nodes connected
Describe the alpha model.
The alpha model starts out with a series of caves (cliques) and at each step randomly rewires one of the cave edges. The number of iterations are given by alpha. Hence links are more likely when two nodes have a common friend.
Describe the beta model.
The beta model istarts with a ring lattice and randomly rewires each edge with probability beta.
What is the difference between the alpha and beta models?
Beta model has global rewiring probability whereas alpha model has a series of iterations.
