Graph Automata -- What Can Social Networks Teach us About Underlying Physical Laws?

Hello 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!

Comments

[Mikaela Keller]

This book , I think is about that...
("LINKED: The New Science of Networks",A. Barabasi)

[Shannon Clark]

Nova, something similar is behind many of the advances in "Network Theory" in the past few years. For general interest look at books such as Synch; Linked; Nexus; and Emergence; as well as books such as Six Degrees: the Science of a Connected Age.

In all of the above there is at least some discussion of what has happened when physicists started looking at networks in other contexts as a source for problems to be solved - very interesting stuff and indeed deeply mathematical.

Also exactly the type of stuff I'm hoping my soon to launch MeshForum (http://www.meshforum.org - up live later this week) will be focused on - this interplay between disciplines, academia and business. The combination of insights and knowledge from the AI community with the fundemental research (and mathematics) of other fields as well as the practical questions, debates, and data sources from the business community (both social networking new businesses and the even larger data sets inside of "big" businesses. Imagine what happens if graph theory and network theory could be applied to the data set of transactions flowing through VISA or money flows through the banking system - could be very informative and valuable.)

More later - I'll post on this on MeshForum in a bit.