Framework built for using graph theory to solve discrete optimization problems

A clique away from more efficient networks
KAUST researchers have shown how the clique problem of graph theory, a branch of mathematics, can be applied to optimize digital communications networks. Credit: ProStockStudio/

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 . The standard representation of a social , 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.

A clique away from more efficient networks
The graph (center) contains two cliques, with members of one clique shown in yellow and of the other clique shown in grey. Credit: KAUST

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 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 ; 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.

More information: Ahmed Douik et al. A Tutorial on Clique Problems in Communications and Signal Processing, Proceedings of the IEEE (2020). DOI: 10.1109/JPROC.2020.2977595

Journal information: Proceedings of the IEEE

Citation: Framework built for using graph theory to solve discrete optimization problems (2020, June 15) retrieved 3 October 2023 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Explore further

Training agents to walk with purpose: Improving machine learning and relational data classification


Feedback to editors