Groups, bridges, and control

A club that split in two

In the early 1970s the anthropologist Wayne Zachary spent three years watching a karate club at a university in the United States. There were 34 members whose friendships he could map: who trained with whom, who met outside class, who sat together. Then a quarrel broke out. The club’s karate instructor, whom Zachary called “Mr. Hi,” and its president and administrator, “John A.,” fell out over the price of lessons. Each man had his supporters, and nobody was neutral for long. The officers dismissed the instructor, and about half the members left with him to start a new club.

Zachary’s question was whether the split could have been predicted from the friendship map alone. He treated the map as a set of pipes carrying information, and asked where the club could be cut in two with the fewest friendships broken. His method assigned 33 of the 34 members to the side they actually joined. The exception was member 9, a supporter of the president who joined the instructor’s camp, reportedly because he was only weeks away from a black-belt test. A person is more than a position in a network. But the network got 33 of 34.

A set of nodes with many more links among themselves than to the rest of the network is called a community. Friends, colleagues, families, and neighborhoods are communities. In 2002 Michelle Girvan and Mark Newman proposed a way to find them automatically: remove, one at a time, the links that lie on the most shortest paths between pairs of nodes, since those are likely to be the bridges between groups, and watch what falls apart. Applied to the karate club, the first split they found agreed almost perfectly with the real one; in their paper, only one member was put on the wrong side. Later methods score a division by its modularity, how many more links fall inside the groups than chance would put there.

The method works without being told anything about the quarrel. That is why the idea spread. The same tools are used to find groups of proteins that work together, of web pages about the same topic, and of people who call each other. A community in a phone network is also a place where information can be trapped: in a 2007 study of the calls of about 4.6 million people, strong ties, those between people who talk often, clustered inside groups.

The strength of weak ties

If groups are dense inside, how does news get from one group to another? The sociologist Mark Granovetter asked that question in a 1973 paper, “The strength of weak ties,” which became one of the most cited papers in sociology. He sorted ties into strong ones (family and close friends) and weak ones (acquaintances) and made an argument from structure. If you have two close friends, they are likely to know each other, so strong ties come in triangles, tight groups where everyone has heard what everyone else has heard. A weak tie, an acquaintance from another part of your life, is far more likely to link you to someone your friends do not know. Weak ties are the bridges between groups, and news that must cross from one group to another has to cross one. He called the triangle with two strong ties and no tie between the third pair the forbidden triad, because it should hardly ever occur.

His evidence came from a study of professional, technical, and managerial men in Newton, Massachusetts, who had recently changed jobs. Among the 54 of the interviewed men who had found their job through someone they knew, only 17 percent saw that person often (at least twice a week). 56 percent saw them occasionally and 28 percent rarely. The people who helped were usually not the closest friends but acquaintances, often someone from an earlier job, who knew about openings that the job seeker’s own circle had not heard of.

The idea has been tested at a much larger scale since. In the mobile-phone study mentioned above, removing the weak ties first made the network fall apart in pieces at a clear threshold, while removing the strong ties first only shrank it. And in 2022 a team including Karthik Rajkumar and Sinan Aral published randomized experiments on LinkedIn’s “People You May Know” feature, covering more than 20 million users over five years and about 2 billion new ties. They did not find that the weakest ties were the best. The relationship between tie strength and finding a job was an inverted U: ties of moderate strength (in an interview, the senior author Sinan Aral put the best point at about ten mutual connections) worked best. Weak ties helped most in more digital industries, and stronger ties helped more in the less digital ones. Granovetter’s central idea, that acquaintances carry news that close friends do not, held up. The detail, that the weakest ties are best, did not quite.

The sociologist Ronald Burt put a price on being the bridge. In a 2004 study of 673 managers who ran the supply chain of a large American electronics company, 455 of them answered questions about whom they talked to, and each wrote down an idea for improving the business. Two senior managers rated the ideas for how valuable they were, without knowing who had proposed them. People who connected groups that otherwise did not talk to each other, whom he called brokers across structural holes, were more likely to voice ideas, less likely to have them dismissed, and more likely to have them rated valuable. Their ideas were better because they had seen what was done in more than one group.

This is one reason the real map of an organization matters. The formal chart shows who reports to whom. The informal network shows whom people actually ask for advice and who passes the news. Rob Cross and Andrew Parker, who studied more than 60 informal networks in companies for their 2004 book on the subject, argued that the formal chart hides the networks that really drive performance. A leader who wants a message to reach the shop floor, or a new hire who wants to learn how things work, will do better to find the people others turn to than to follow the boxes on the chart. And a company that puts its new recruits all in one building, apart from the old teams, builds a community and no bridges.

Can a network be steered?

The last question in this course is the boldest. If we know how a network is wired, can we control it: push it from any state to any other by acting on a few of its nodes? In engineering, the question has a precise form, introduced by the mathematician Rudolf Kálmán around 1960. A system is controllable if, by adjusting its inputs, you can steer it from any starting state to any other in a finite time.

Think of a car. A modern car has thousands of parts, perhaps tens of thousands if you count every nut and bolt. But you steer it through three or four of them: the steering wheel, the accelerator, the brake, and sometimes the clutch. The car has been built so that those few controls move all the rest. What the 2011 paper “Controllability of complex networks” asked is the reverse question: given a wiring diagram and nothing else, can you work out which few nodes you would need to control?

The answer starts from a simple example. If a node sends the same signal to two other nodes, those two can never be driven independently: they always move together. To steer them separately, you need a second input. So control is not only a matter of there being a path from the controller to every node. The controller must be able to send each node a different piece of information, which depends on how the wiring is arranged. Kálmán’s test says whether a given set of inputs works, but it does not say which nodes to choose.

The 2011 paper found the choice by turning control into a game that has nothing to do with control, called matching. You may paint some of the arrows red, on one condition: no two red arrows may leave the same node, and no two may enter the same node. Find the largest set of arrows you can paint. A node that a red arrow points into is matched: it is steered by one of its neighbors. A node that no red arrow enters is unmatched, and nothing in the network can steer it separately. The theorem is that the unmatched nodes in a largest matching are the driver nodes, the ones you must control directly. If the network has N nodes and a largest matching of M arrows, you need at least N − M inputs, and at least one. Matching can be solved quickly even on very large networks, with a standard algorithm (Hopcroft and Karp, 1973). Play the game.

The paper reported that how many driver nodes a network needs depends mainly on its degree distribution: dense, uniform networks need few, while sparse networks with a few hubs need many. And the driver nodes, they found, tended to avoid the highest-degree nodes. A follow-up in 2013 sorted nodes into three kinds: critical nodes, which must be controlled in every solution; redundant nodes, which never need to be; and intermittent nodes, which are in some solutions and not in others. In this reading, the idea is turned into leadership advice: in a hierarchy, a few nodes must be reached and the rest follow, while a more distributed network, in which many nodes are sometimes needed, is better suited to innovation than to efficient production. That is a suggestion, not a result. The theorem is about a mathematical model.

What the maps show

The course has traveled from a tree in Ohio to a theory of control. Here is what each step amounts to, with its honest status.

• Small worlds. In large networks any two nodes are a few steps apart (4.7 steps on Facebook in 2011), because reach multiplies. Well supported; “six” is a rough figure and not a law.
• Hubs. Real networks have far larger hubs than random ones, a pattern with a power-law shape. Heavy tails are common; pure power laws are less common than first claimed.
• The rich get richer. Growth with preferential attachment, helped by fitness, produces hubs and explains why early movers lead but need not win. A good first model, with other mechanisms in some networks.
• Robust yet fragile. Hub-dominated networks survive accidents better than attacks, and failures cascade. Well supported in models; how it applies to a particular real network depends on the details, as in the Internet debate.
• Spreading. Hubs and superspreaders speed up diseases and ideas; your friends have more friends than you do. Well supported; the exact “no threshold” result is for idealized infinite networks.
• Groups and bridges. Communities are dense inside and joined by a few weak ties that carry the news. Strongly supported, including by a very large experiment, with the refinement that moderately weak ties work best.
• Control. A few driver nodes can in principle steer a network. An exact result in a model; limited in practice.

The same ideas have been put to work in business. In 1998 Sergey Brin and Larry Page described a way to rank web pages in which a link from an important page counts for more than a link from an unimportant one, so that a link is a vote weighted by the voter’s own standing. That is a network idea, and the company they founded that year used it. A broader claim, that today’s most valuable companies are network companies, needs care. Some of them run platforms where each new user makes the service more useful to the others, which is a network effect. Metcalfe’s law says the value of such a network grows as the square of the number of users; in 2006 Bob Briscoe, Andrew Odlyzko, and Benjamin Tilly argued that it grows more nearly as n times log n, because not all connections are equally valuable. Others of the largest companies mostly sell chips, devices, or software. The lesson is the question to ask: what is the network behind this system, and who are its hubs and bridges?

And so the course ends where it began, with the idea that to understand a complex system you must look at the connections as well as the parts. A cascade, a market bubble, a rumor, and a pandemic are things that happen in networks. They are not explained by looking at one node at a time.