BLOG@CACM
Architecture and Hardware

Can Transaction Costs Explain Scale-Free Networks Born by Preferential Attachment?

Posted

Originally published on the I Think blog.

Online human networks are highly centralized, with a few nodes raking in most connections. The conventional wisdom is that this is the product of so-called "preferential attachment." In Barabasi and Albert's [1] formulation, new nodes (connectors) added to any network will prefer to attach themselves to the existing ones preferentially, targeting the ones that already have a lot of connections. The reasons, especially in social networks, are simple. Everybody loves a winner. This idea was explored in depth in the realm of human-to-human networks online [5].

However, there might be another, complementary, explanation for preferential attachment: transaction costs. The value of being connected to a highly-connected node derives not only from what that node provides you: access or visibility. By connecting to an already densely connected node, you have a cheaper, quicker, and more comprehensive understanding of the network as a whole. The knowledge you get from observing the highly central node lowers the cost of interaction with other, more distant nodes. In a word, centralization leads to more efficient communication and control, which leads to lower transaction costs, which finally increases the amount of useful work each node can spend on the core non-communication tasks [2].

Let us make this simpler. Any social and collaborative system (and all networks are established to support such systems) requires their members to divide their useful work into at least two types of activities. First, there are the core activities of the network. Second, there are activities that help the users monitor the state of the network. The latter activities help the users decide on their priorities: when and how to engage in core activities, the very nature of their work, the things to do or to avoid, and so on.

Naturally, both the connectors and the network as a whole will benefit from maximizing the time spent on core activities and minimizing the time spent on surveillance activities, the latter incurring only transaction costs. Highly decentralized networks impose a higher transaction and communication cost on the connectors than centralized networks. The more decentralized a network, the lower the communication and transaction costs. The more centralized the network, the lower the average transaction costs for ordinary nodes.

This can be easily demonstrated. Imagine we have a fish-net network, in which each node, except those at the edges, is connected by the same number of other nodes. In a classic topology, each node would be connected to four other nodes. Those, in turn, would be connected to the other three and so on. Any node needs to invest a certain amount of useful work on communication and surveillance: how does the network as a whole perform, what needs to be done, who does it, and so on. Since all connectors need to go through their neighbors to accomplish this, and the more extensive the network, the more each node is dragged into spending time on surveillance for itself and the others. The more comprehensive an image is desired, or the more far-reaching the communication, the more all the connectors will have to spend communicating with each other, requesting, receiving, and sending more information. Communicating needs time and useful work. This affects not only the nodes directly asking for information, but all the nodes through which information flows. As decentralized networks are bucket brigades, for each bit of information to get to the destination, many hands need to handle it. Communication requests will increasingly burden the networks. With increases in network size, transaction costs increase to the point where all nodes need to spend their entire useful work merely on monitoring the network status. For large-enough networks, the available aggregated work of the connectors might not cover the communication needs of the system as a whole. Such networks waste all their members' useful work in transaction costs. To work at all, they need to break up into subnetworks until sufficient useful work is liberated from the realm of communication and redirected to core activities.

Now, imagine a highly centralized network, with a limited number of highly connected nodes and many others dependent on them, as relays and further on, until one reaches ordinary connectors (nodes). Such a hierarchical network imposes on each average node a minimal transaction cost. The central nodes, by their massive number of inbound connections, receive at almost no cost to themselves huge amounts of information about the network. The processing costs are non-trivial, yet they are significantly lower if the relay nodes by which the information arrives at the hyper-connectors do some processing of their own. Upon final processing and collation of information, the most central nodes disperse the information by discrete and distilled batches through their relay subordinated nodes. The same distilled data is sent to many nodes, in a broadcast-like model: one to many. The transaction cost for the end connectors becomes minimal, as they only need to spend useful work on requesting and consuming the information in short and infrequent bursts.

From this perspective, preferential attachment makes much sense for the connectors. Preferentially connecting to nodes that control a lot of information lowers transaction costs. Also, networks that centralize faster can grow faster and larger, presenting an evolutionary advantage, and attracting more new nodes faster. Furthermore, networks that do not centralize soon will crash and break up under the pressure of transaction costs into smaller networks. Of course, even successful networks will encounter an absolute limit to growth, since even hyper-centralization cannot keep up with the increasing aggregated transaction costs.

This idea of explaining preferential attachment via transaction costs is relatively easy to check both via simulation (we are working on a few experiments) and empirical research on human collaborative networks (we are working on that, as well, using Wikipedia co-editorial networks as a testing ground).

As a side note, I had a brief conversation in March 2018 with Albert Laszlo Barabasi, the proponent of the preferential attachment theory, about the role and importance of transaction costs in the emergence of scale-free networks by preferential attachment. He told me that so far, his attention was not focused much on this approach and that only some economists [3][4] worked on the spatial aspect of the problem, where transaction costs are interpreted as transportation costs. Time to crank some research to test this idea! We might be onto something. If you have suggestions, ideas, or citations of papers that look at this issue, please let me know.

 

[1] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509–512.

[2] Matei, S. A. and Britt, B. C. (2017). Structural Differentiation in Social Media: Adhocracy, Entropy, and the "1 % Effect" (1st ed.). Springer Publishing Company, Incorporated.

[3] Boschma, R. and Frenken, K. (2010). The spatial evolution of innovation networks. A proximity perspective. The Handbook of Evolutionary Economic Geography, 120–135.

[4] Hearnshaw, E. J. S., and Wilson, M. M. J. (2013). A complex network approach to supply chain network theory. International Journal of Operations & Production Management, 33(4), 442–469. https://doi.org/10.1108/01443571311307343

[5] Kunegis, J., Blattner, M., and Moser, C. (2013). Preferential Attachment in Online Networks: Measurement and Explanations. In Proceedings of the 5th Annual ACM Web Science Conference (pp. 205–214). New York, NY, USA: ACM. https://doi.org/10.1145/2464464.2464514

 

Sorin Adam Matei is Associate Dean of Research and Professor of Communication at Purdue University, where he also serves as Director of the FORCES initiative leading research teams that study the relationship between technological and social systems using big data, simulation, and mapping approaches.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More