使用图论解决离散优化问题的框架

据悉，使用图论的框架（考虑网络的编码方式）可以帮助提高数字通信网络的效率。

为了对社交网络进行建模，没有任何一个数学分支比图论更完整。实际上，社交网络的标准表示是图。它包括一组点，其中一些线连接在一起。这些点表示网络的成员，而线表示它们之间的连接。

与KAUST的TareqAl-Naffouri和Mohamed-SlimAlouini一起工作的是，现任Caltech的前KAUST学生AhmedDouik和现任Effat大学的前博士后HayssamDahrouj，发现了图形理论可以进一步应用的另一个领域：通信和信号处理。

Dahrouj说：“我们已经建立了一个使用图论来解决离散优化问题的框架，并且效果极佳。”他们的方法是将给定的数字通信网络表示为图形，然后在其中找到“clique”。在图论中，这被称为解决“clique问题”。

在任何图中，集团是点的子集，其中每个点都与其他每个点相连。在社交网络中，这是一个组，其中每个成员都是该组中每个其他成员的朋友。例如，Facebook解决了集团问题，以制定最佳的朋友建议和广告，以发送其数以百万计的每个成员。

图表（中心）包含两个小组，一个小组的成员以黄色显示，另一小组的成员以灰色显示。

在先前的工作中，Douik和Dahrouj展示了如何使用相同的方法来优化通信网络。例如，将无线数据馈送给经过的汽车的基站可以进行编程，以发送一次通用的数据包，而不是重复发送到各个车辆。Douik认为，将集团问题应用于大型网络可以将其吞吐量提高多达30％。

由于任何图的复杂性都随着其大小的增长而呈指数增长，因此计算机需要聪明的算法来解决除最小图以外的所有图的集团问题。杜伊克说：“在一个多世纪的图形理论研究中，已经描述了许多算法；其中一些算法是在计算机出现之前出现的。”“这意味着有大量的文学作品在等待借鉴。”

该方法的另一个优点在于其未来的适用性。随着网络规模和复杂性的增加，优化带来的收益也随之增加。明天的物联网将拥有更多用户，其中5G和6G可以容纳更多的数据。