A clique away from more efficient networks

June 14, 2020

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


King Abdullah University of Science & Technology (KAUST)

Related Social Network Articles from Brightsurf:

'Social cells' related to social behavior identified in the brain
A research team led by Professor TAKUMI Toru of Kobe University's Graduate School of Medicine (also a Senior Visiting Scientist at RIKEN Center for Biosystems Dynamics Research) have identified 'social cells' in the brain that are related to social behavior.

Grooming behavior between dairy cows reveals complex social network
Like humans, cattle are social creatures with complex relationships that change as group dynamics evolve.

Loneliness alters your brain's social network
Social media sites aren't the only things that keep track of your social network -- your brain does, too.

First map of proinsulin's 'social network' reveals new drug target for type 2 diabetes
Scientists at Sanford Burnham Prebys Medical Discovery Institute have mapped for the first time the vast network of proteins that interact with proinsulin, the protein the body normally processes into insulin.

Social media influencers could encourage adolescents to follow social distancing guidelines
Public health bodies should consider incentivizing social media influencers to encourage adolescents to follow social distancing guidelines, say researchers.

Social grooming factors influencing social media civility on COVID-19
A new study analyzing tweets about COVID-19 found that users with larger social networks tend to use fewer uncivil remarks when they have more positive responses from others.

Half billion-year-old 'social network' observed in early animals
Some of the first animals on Earth were connected by networks of thread-like filaments, the earliest evidence yet found of life being connected in this way.

Social isolation during adolescence drives long-term disruptions in social behavior
Mount Sinai Researchers find social isolation during key developmental windows drives long term changes to activity patterns of neurons involved in initiating social approach in an animal model.

Exploring a genome's 3D organization through a social network lens
Computational biologists at Carnegie Mellon University have taken an algorithm used to study social networks, such as Facebook communities, and adapted it to identify how DNA and proteins are interconnected into communities within the cell nucleus.

'Surprise' out-of-network bills after in-network elective surgery
Claims data from a large health insurer were used to examine how often patients unexpectedly receive out-of-network bills after having in-network elective surgery.

Read More: Social Network News and Social Network Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.