Graph Automata — What Can Social Networks Teach us About Underlying Physical Laws?
January 27th, 2004Hello all, I have been thinking about the general problems of social networks on the Internet. It occurs to me that these issues are closely related to digital physics. For more on digital physics see the work of Ed Fredkin, Stephen Wolfram, Norman Margolus, Tomasso Toffoli, and other pioneers of the field of cellular automata.
In the past I have worked informally on cellular automata at MIT in the lab of Fredkin, Margolus and Toffoli — and in particular that led me to get interested in what could be called “graph automata” — rules that operate on arbitrary graphs in a manner that is similar to the way that cellular automata operate on cells in rigidly defined neighborhood topologies. The general concept is that the structure of a graph can be optimized for various parameters in a bottom-up, iterative, emergent fashion by running local rules at each node based on the neighborhood structure around each node (taking into account the number of arcs around each node, the directionality of arcs if any, and the states of nodes if any). There is a general class of rules that we could call “graph automata” that are quite interesting to study because in many ways they are better metaphors for physics than simple CA’s, in my opinion.
In any case, that’s not the point of this note. Instead, I would like to propose that one way to discover the “general laws” of digital physics might be to study social networks. Social networks are an interesting “macro-level” phenomenon that could be considered to be useful analogs for discovering the general properties of physical information networks. They are comprised of nodes connected by arcs in which information flows. We could view all physical systems through this lens and perhaps learn quite a bit from this approach.
Currently social networks on the Internet are either totally informal and decentralized or totally centralized and formal. However in either case they are not being effectively optimized because nobody knows how to optimize them.
To optimize a social network we need to continually evolve the graph as members join, interact and form and end relationships. As the network evolves the paths that information takes between interacting (or frequently interacting) members are therefore evolved (and are hopefully optimized in the process). In other words, if the goal is to optimize the communications between nodes in the network, then the rule we choose should seek to continually optimize the signal to noise ratio of each node. Another way to say this is that the network seeks to help each node optimally balance its connectivity against information overload.
It seems to me that this is a general principle that may apply in many domains — including perhaps digital physics. It reminds me of general relativity in certain respects. Perhaps there are people out there, more mathematical than myself, who are able to take this idea further? I have a strong hunch that this is a clue to a general physical law that might be useful at many levels of scale, and for many purposes. Is there a simple rule that evolves graphs to optimize relationships among interacting nodes? If so, I would not be surprised if this rule generates dynamically changing graphs that obey the principles of Relativity. The rule we discover could be of great value in physics, biology, chip design, communications and network architectures, artificial intelligence and machine learning, information architectures and search, and social network architectures, as well as many other fields, like economics, for example.
While all of this is speculative and I am not a mathematician or a physicist, I have a long history in cellular-automata and AI and I have a strong hunch that there is something here worth looking into further. Keep me posted!
Here is a link to an article about this — I would enjoy hearing your comments!