Framework built for using graph theory to solve discrete optimization problems

A framework that uses graph theory, which considers how networks are coded, could help make digital communication networks more efficient.

For modeling social networks, no branch of mathematics is more integral than graph theory. The standard representation of a social network, in fact, is a graph. It comprises a set of points with lines joining some of the points. The points represent the network's members, while the lines represent the connections between them.

Working with KAUST's Tareq Al-Naffouri and Mohamed-Slim Alouini, former KAUST student Ahmed Douik now at Caltech and former postdoc Hayssam Dahrouj now at Effat University, have found a further area to which graph theory can be usefully applied: communications and signal processing.

"We've built a framework for using graph theory to solve problems of discrete optimization with excellent results," says Dahrouj. Their method is to formulate a given digital communication network as a graph and then find "cliques" within it. In graph theory, this is known as solving the "clique problem."

In any graph, a clique is a subset of points in which each point is connected to every other point. In a social network that means a group in which each member is friends with every other member in the group. Facebook, for example, solves the clique problem to work out the optimum friend suggestions and advertisements to send each of its many millions of members.

In previous work, Douik and Dahrouj showed how communications networks can be optimized using the same approach. A base station feeding wireless data to passing cars, for example, can be programmed to send data packets for common use once instead of repeatedly to individual vehicles. Applying the clique problem to large networks can, Douik reckons, improve their throughput by up to 30 percent.

Because the complexity of any graph increases exponentially as it grows in size, computers need clever algorithms to solve the clique problem for all but the smallest graphs. "A huge number of algorithms have been described in more than a century of research into graph theory; some before the appearance of computers," says Douik. "This means there is a rich body of literature waiting to be drawn on."

Another beauty of the approach lies in its future applicability. As networks increase in size and complexity, so do the gains from optimization. Tomorrow's internet of things will feature many more users, with 5G and 6G enabling much larger volumes of data to be accommodated.