Questions & explanations
1. Give an example of a simple network where the observability Gramian is not full rank, and explain why.
Consider two nodes connected by a single directed edge from node 1 to node 2. Only node 2 is measured. The system has state vector [x1, x2]. The output is just x2. The dynamics: x1 influences x2 but x2 doesn't influence x1. From output x2 alone, you cannot know x1 because x1 could be anything as long as it doesn't affect x2? Actually it does affect x2 through the edge. But if you only measure x2, you can reconstruct x1 if you know the dynamics? Let me correct: With only output x2, the observability Gramian might be rank 1 because you can only observe x2 but you can infer x1 from its effect on x2? In linear systems, if the output includes x2, and x1 affects x2, then x1 is observable from the derivative of x2? Actually, observability condition: the observability matrix has rank 2? For a simple system A=[0 0;1 0], C=[0 1], the observability matrix is [C;CA] = [[0,1],[1,0]] which has rank 2, so it's observable. So need a better example: Consider two separate nodes with no connection, each independent, and only one node measured. Then the other node is unobservable. So example: two isolat
2. Compare minimum driver nodes for a directed tree vs a directed cycle of the same number of nodes.
For a directed tree (a spanning tree with root), the minimum driver nodes is usually 1 (the root). For a directed cycle (each node has one incoming and one outgoing edge), the number of driver nodes is also 1 (any node can be driver). But if the cycle is long, a matching covers all nodes? Actually a cycle has a perfect matching? No, a cycle of odd length? Wait, for a directed cycle, each node has indegree=1, so maximum matching size = n-1? Let's correct: In a directed cycle, each node has exactly one incoming edge, so maximum matching pairs all nodes except one? Actually the maximum matching in a cycle is n-1 if it's a directed cycle? Correct: For a directed cycle, you can match n-1 edges, leaving one unmatched node as driver. So for n=5, you need 1 driver node. For a tree, you also need 1 driver. So both need 1 driver node, but the tree has a root.
3. Give an example of a network where the giant component size is zero.
A sparse random network with average degree below one has no giant component. For example, a random graph with 100 nodes and only 40 edges (average degree 0.8) will be fragmented into many small components. No single component contains a significant fraction of nodes. Similarly, a regular tree with degree 2 (a line) has no giant component because it is a single infinite line but not a giant component in a finite sense? Actually, in infinite networks, a regular tree has no giant component? Let's be careful: For infinite trees, the giant component is the whole tree, but in finite networks, size is relative. Better example: a network of isolated nodes has zero giant component size. But that's trivial. Use: In the Erdos-Renyi model, if average degree < 1, the largest component size scales as log N, not linear in N.
4. In a social network, a celebrity with many followers has high degree but low betweenness. Explain.
A celebrity has high degree because they have many followers (direct connections). However, their followers may not connect to each other, so the celebrity is not a bridge between different groups—most paths go through their followers but not necessarily through the celebrity. Betweenness counts how often a node lies on shortest paths; celebrities often only connect to their fans, who already connect to each other through the celebrity? Actually, if fans connect only via the celebrity, the celebrity has high betweenness. But if fans are random, maybe not. Better example: a popular person with many friends within one circle, so they don't bridge different circles. They have high degree but low betweenness because information flows without them as key intermediary.
5. What does the Kuramoto model describe?
The Kuramoto model is a mathematical model that describes how many oscillators (things that move back and forth, like pendulums or flashing lights) can start to move together when they are weakly connected. Each oscillator has its own natural rhythm, but when coupled, they can synchronize, meaning they all move at the same frequency. The model uses a simple equation where each oscillator's phase (its position in its cycle) changes based on its natural frequency and the average of all other oscillators. This helps scientists understand collective behavior in systems like fireflies flashing together or brain cells firing. It was introduced by Yoshiki Kuramoto in 1975 and is a key model for synchronization.
6. Compare the role of damping in the swing equation with the role of coupling strength in the Kuramoto model.
In the swing equation, damping represents friction or control that reduces oscillations; it helps stabilize the system by dissipating energy. In the Kuramoto model, coupling strength determines how strongly oscillators influence each other. Both parameters affect synchronization: in power grids, damping helps achieve entrainment by reducing transient swings; in the Kuramoto model, increasing coupling strength helps overcome frequency differences. However, damping directly reduces speed deviations, while coupling directly synchronizes phases. Without damping, the swing equation would have undamped oscillations, similar to the Kuramoto model with no damping but with inertia.
7. Explain how the configuration model with degree-degree correlations can be used to generate a network that mimics a real-world email network.
First, you extract the degree sequence and the degree correlation pattern from the real email network (e.g., users' out-degree and whether high-degree users email each other). Then you use the configuration model with those inputs: you assign each node a certain number of stubs (half-links) equal to its degree, and you pair stubs in a way that preserves the desired correlation. For example, if the real network is disassortative (high-degree users email many low-degree ones), the model will create more such pairs. The resulting random network will have the same degree sequence and correlation structure, allowing you to test hypotheses about, say, information spreading.
8. Compare structural controllability with the Kalman rank condition for control of networks.
The Kalman rank condition is an exact numerical test: you need exact values of A and B. Structural controllability considers only the pattern of connections (zeros and nonzeros) without precise weights. A network is structurally controllable if there exist some nonzero weights that make it controllable in the Kalman sense. It uses graph theory: a network is structurally controllable if every node is reachable from a driver node and there are no 'dilations' (a set of nodes with more outgoing than incoming influences). The Kalman condition is stricter because it requires exact rank, but structural controllability gives a generic guarantee for almost all weight choices.
9. How would you tell if a real network has degree-degree correlations compared to a random network with the same degree sequence?
You can compute the assortativity coefficient, which measures the correlation between degrees of connected nodes. A positive value means similar-degree nodes connect (assortative), negative means opposite-degree nodes connect (disassortative). Then compare this coefficient to the average value from many random networks generated by the configuration model without correlations. If the real network's coefficient is significantly different, it has degree-degree correlations. For example, a social network might show positive assortativity (friends have similar number of friends), while the internet shows negative assortativity (hubs connect to low-degree nodes).
10. What is self-organization in engineering and design?
Self-organization in engineering and design means that many simple parts follow simple rules and together create a useful pattern or behavior without a central controller. For example, in a swarm of robots, each robot follows a few rules like 'follow the robot in front' and 'avoid crashing'. Together they form a group that can move objects or explore an area. This is different from a top-down design where a central computer tells each robot exactly what to do. Self-organization makes the system strong because if one robot fails, the group still works. It is used in traffic lights, communication networks, and even in designing buildings that adapt to weather.
11. How does Kleinberg's model differ from the Watts-Strogatz small-world model?
Watts-Strogatz (WS) model starts with a regular ring lattice and rewires edges with probability p, creating both short-range and some random long-range links. This yields high clustering and short average path length. However, WS does not specify a particular distribution for long-range links; it's uniform. Kleinberg's model instead places long-range links with a probability that depends on distance (a power law). Moreover, Kleinberg is concerned with decentralized search performance, not just the existence of short paths. In WS, greedy search is inefficient, while in Kleinberg with optimal alpha, it is fast. So, Kleinberg's model is more about navigation.
12. How would you use MCMC to estimate the parameter for the triangle term in an ERGM?
You would write an MCMC algorithm (e.g., using the ergm package in R). Set the observed network as data. Start with some initial parameter for the triangle term (maybe 0). Then run MCMC: at each step, propose a small network change and accept/reject based on the change in probability. After many steps, compute the average number of triangles from the sampled networks. If this average is higher than the observed number, you decrease the parameter; if lower, increase. Repeat until the average matches the observed triangle count. This iterative process yields the maximum likelihood estimate. The final parameter tells the strength of triangle formation.