Efficient Algorithms for Complex Networks

Question

Most standard works on random graphs focus on $G_{n,p}$ and random regular graphs. However, such models are far from a good abstraction to describe the types of networks that one typically encounters in the real world.

There are several simple models that mimic the behavior of real-world graphs, sometimes called Complex Networks.

There are many graph problems that become easier in the setting of $G_{n,p}$, such as finding a Hamiltonian path, finding a perfect matching, etc. I am sure that similar work has been done for random complex networks, but I haven't been able to find a good book or survey paper on the subject. I must be using the wrong terminology.

I would be grateful if someone could point me towards something like that, or tell me what the subject of efficient algorithms for complex networks is called in the literature.

Answer 1

There are currently serious efforts devoted to algorithms taking into account usual properties of complex networks, either in their design (use these properties to be efficient) or in their analysis (show that, if the input graph has these properties, then the algorithm has low complexity).

Since most complex networks met in practice are sparse, let me first say that any complexity expressed in terms of the number of edges (instead of the squared number of vertices) is of interest in this context. But I do understand that you actually have more advanced complex network properties and complexity analysis in mind.

My 2006 paper about triangle counting and listing provides a good illustration, I think. There, I used the fact that most complex networks met in practice have very heterogeneous degrees. I proposed a very simple algorithm makes a distinction between low- and high-degree vertices, and proved its algorithmic complexity as a function of the graph degree distribution.

Many such examples exist in the literature. For instance, the arboricity and core value have been used to enumerate $k$-cliques. However I am not aware on any survey devoted to them.