Motif Iteration Model for Network Representation

Lintao Lv, Zengchang Qin, Tao WanarXiv 2017 · arXiv

TL;DR

This paper introduces the Motif Iteration Model (MIM) and the Vertex Reordering and Arranging (VRA) algorithm to bridge the gap between graph theory and computer vision. By transforming complex network adjacency matrices into consistent, visually structured binary images, the authors enable standard Convolutional Neural Networks (CNNs) to classify network types with near-perfect accuracy.

What Problem Does This Paper Address?

Understanding the structure of social networks is fundamental to social media mining, yet representing these structures effectively remains a challenge. Researchers typically choose between two paths: count-based motif methods (which look at local sub-graphs but miss the big picture) or global adjacency matrix methods (which capture the whole structure but are highly sensitive to how nodes are indexed).

The core problem is that the same network can look completely different in an adjacency matrix depending on the arbitrary order of its vertices. This makes it difficult to use powerful image-recognition tools like CNNs to "see" the underlying patterns of a network. The authors seek a way to create a unique, visual "fingerprint" for a network that preserves both local building blocks and global topology.

Methods

The authors propose a two-part framework:

  1. Motif Iteration Model (MIM): This model views complex networks as recursive structures. It starts with basic "motifs" (small subgraphs of 3 or 4 nodes) and iteratively replaces nodes with these motifs to build larger, more complex hierarchies. A "Standard" version (SMIM) adds constraints to ensure that nodes in adjacent locations are preferentially linked, creating a more uniform visual structure.

    Fig. 1. Displays the Motifs Iteration Model of the networks under different number of nodes. There is an NCN network with parameter k = 2. Black nodes and segments are denoted as first-level motifs, red nodes and line segments represent second-layer motifs. The link between the second-layer motifs is called the second-link.
  2. Vertex Reordering and Arranging (VRA): This is the paper's primary algorithmic contribution. VRA is a heuristic, greedy algorithm that reorders the vertices of a network based on their degree and a specific priority order. By placing "important" vertices in the center and arranging secondary vertices symmetrically around them, it transforms a chaotic adjacency matrix into a structured adjacency matrix binary (amb) image.

    Fig. 2. This is an example of a three-node motifs with its corresponding amb image. The first line is the same motifs structure with different node indices. The second line is network’s amb image. Though the structure of the network is identical, but the amb images are different, we need one unique image for the same network structure regardless node indices.

Datasets

The study evaluates the model using four classic synthetic network types, each with 100 to 200 vertices:

  • Erdős-Rényi (ER): Random networks.
  • Nearest-Neighbor Coupled (NCN): Regular networks where each node links to its neighbors.
  • Watts-Strogatz (WS): Small-world networks.
  • Barabási-Albert (BA): Scale-free networks.

For real-world application, they analyze the Zachary’s Karate Club network, a famous social network of 34 members.

Key Insights and Ideas

  • Networks have "Textures": By applying VRA, the authors show that different network models produce distinct visual patterns. A random network looks like static, while a small-world network reveals clear, symmetric "waves" or grids.

    Fig. 3. An illustration of the VRA effect for small-world networks. (a) and (b) represent the amb image after random generation and VRA processing respectively.
  • Symmetry as a Feature: The VRA algorithm specifically targets symmetry. This is crucial because CNNs are excellent at detecting symmetric patterns and textures, which are otherwise hidden in a raw adjacency matrix.

  • Hybrid Composition: The authors suggest that real-world social networks aren't just one type. They propose a decomposition formula where a network like Zachary’s Karate Club can be described as a weighted combination (e.g., 50% BA, 43% WS, and 7% NCN).

Key Results

The effectiveness of the VRA algorithm was tested by training a CNN to classify the four synthetic network types.

  • Without VRA: The CNN struggled, particularly with Watts-Strogatz (WS) networks, achieving only 79% recall. The overall precision for NCN networks was also lower at 84.3%.
  • With VRA: The classification performance jumped to 100% precision and 100% recall across all network types. The VRA processing successfully removed the noise caused by random node indexing, allowing the CNN to identify the "nature" of the network perfectly.

Limitations and Future Work

  • Scalability: The experiments focused on medium-sized networks (up to 200 nodes). The authors do not explicitly discuss how the computational complexity of the VRA algorithm scales for massive networks with millions of nodes.
  • Directed Graphs: The current study is limited to undirected graphs. Extending this visual representation to directed social interactions (like Twitter followers) remains a future challenge.
  • Real-World Complexity: While the paper suggests a "rough solution" for decomposing real networks into basic types, a more robust, automated method for community-based decomposition is needed to handle large-scale social data.

Summary updated

Abstract

Social media mining has become one of the most popular research areas in Big Data with the explosion of social networking information from Facebook, Twitter, LinkedIn, Weibo and so on. Understanding and representing the structure of a social network is a key in social media mining. In this paper, we propose the Motif Iteration Model (MIM) to represent the structure of a social network. As the name suggested, the new model is based on iteration of basic network motifs. In order to better show the properties of the model, a heuristic and greedy algorithm called Vertex Reordering and Arranging (VRA) is proposed by studying the adjacency matrix of the three-vertex undirected network motifs. The algorithm is for mapping from the adjacency matrix of a network to a binary image, it shows a new perspective of network structure visualization. In summary, this model provides a useful approach towards building link between images and networks and offers a new way of representing the structure of a social network.
BibTeX
@misc{lv2017motif,
  author = {Lintao Lv and Zengchang Qin and Tao Wan},
  title = {{Motif Iteration Model for Network Representation}},
  year = {2017},
  eprint = {1710.00644},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.00644},
}
Figure