New Tool Focuses on Links Within Networks

Community detection algorithms used to evaluate how groups are clustered or partitioned are being used to determined how similar groups tend to either bind closer together or break apart. That capability is critical for data analysts trying to understand the structure of complex networks.

A new computational tool described by researchers at the University of Southern California’s Viterbi School of Engineering promises to streamline the ability to identify hidden connections among groups and individuals.

Social networks are among the best examples of community structures containing diverse connections. The USC researchers recently reported on a geometric approach to community identification in complex networks using a method called Ollivier-Ricci Curvature. “Ollivier-Ricci curvature which offers a natural method to discover inherent network community structures,” lead author Jayson Sia said.

The researchers extended the method for measuring curved surfaces such as Earth to networks. In their experiment, “positively curved” edges formed a “well connected” community—a sort of Pangaea of  interrelationships.

By contrast, “negatively curved” edges were interpreted as “bridges” between communities. Breaking those links would isolate and block the flow of information between communities.

The application of O-R curvature to graphs is said to uncover the structure and geometry of a community via “optimal transport,” the researchers noted—as in the fastest way between two points on a map is a straight line. Among the goals of community detection is identifying a “robust transport of information” within a network, whether social or wireless.

Indeed, the researchers noted that the approach has been applied to areas such as quantum computing, network analysis and wireless networking architectures.

The community detection approach using O-R curvature was able to capture a pair of structural properties of complex networks. First, it identified a network edge and encoded its “shortest path characteristics.”

Second, it graphed the frequency of network edges.

Additional research will focus on how the O-R curvature method can be used to discern the building blocks of complex networks and whether the curvature method can “provide algorithmic hints towards solving the hard problem of community identification,” the researchers said.

Among the practical applications are helping neuroscientists determine which parts of the brain are working on the same functions—an insight that would allow other parts of the brain to assume functions from injured tissue. Other emerging applications include predicting potential drug side effects or interactions that currently require years of experimentation.

The USC researchers have released the code for their community detection code here.

Separately, MIT researchers have proposed a community detection algorithm that combines existing search strategies that include merging two communities, splitting a single community into two and moving nodes between two distinct communities.

Recent items:

Rethinking Architecture at Massive Scale

Why Knowledge Graphs Are Foundational to Artificial Intelligence