Crossing Layers: Optimizing Influence Maximization in Distributed Mobile Social Networks

TL;DR

While Influence Maximization (IM) is a well-studied problem for centralized platforms like Facebook or Twitter, it faces a massive "communication wall" when moved to decentralized Mobile Social Networks (MSNs). This paper introduces a cross-layer strategy called ASMTC that selects "Agents" to act as representatives for local groups of friends. By shifting computation to these agents, the authors reduced message overhead in the underlying physical network by up to 82% without losing influence performance.

The "Communication Wall" in Mobile AD-HOC Networks

In a standard social network, a central server calculates who the best "seeds" (influencers) are. However, in an MSN (built on Bluetooth or WiFi-Direct), there is no central server. Every node only knows its immediate friends. To find the best seeds, nodes must exchange messages to simulate influence spread—a process that is computationally and communicatively expensive.

The problem is Cross-Layer Disconnect: A friend in your "Social Layer" might be 10 hops away in your "Physical Layer" (MANET). Sending multiple simulation messages across these 10 hops for every seed candidate quickly overwhelms the network.

Methodology: The Agent Selection Strategy

To bridge the gap between social connections and physical distances, the authors formulated the Agent Selection Problem (ASP). The goal is to choose a subset of nodes as agents that minimize the total "hops" traversed during the seed selection process.

1. Distributed Agent Selection (DAS)

In this phase, the algorithm greedily selects nodes that can provide the largest reduction in message overhead. If an agent and the node it represents are the same (or physically close), the influence simulation can be done locally with zero or minimal network cost.

2. Message Overhead Reduction (MOR)

Since greedy selection doesn't always find the global optimum, the MOR phase uses three sub-steps—Trying, Checking, and Backward Tracking—to fine-tune agent assignments. If a node finds a better nearby agent, it switches, provided the overall network overhead doesn't increase.

In the figure above, the logical social connections (MSN) are mapped onto the physical multi-hop layout (MANET).

Experimental Validation

The authors tested their algorithm using two major datasets: NetHEPT (15k nodes) and NetPHY (37k nodes). They compared the standard CELFGreedy algorithm (a baseline for IM) against their agent-enhanced version.

• Overhead Reduction: The results shown in Figure 5 are striking. Even with a small percentage of nodes acting as agents, the message overhead drops precipitously.
• Efficiency: The additional overhead required to select the agents is negligible (approx. 1.5 x 10^5 messages) compared to the millions of messages saved during the seed selection iterations.

Figure 5: Demonstrating how increasing the number of nodes selecting agents drastically reduces the MANET overhead.

Final Insights

The true value of this work lies in its Cross-Layer Insight. Most researchers treat the social layer as an abstract graph, ignoring the physical reality of how bits move between devices. By treating the MANET and MSN as a unified system, the authors proved that distributed viral marketing is not just a theoretical possibility but a practical reality for mobile devices.

Limitations & Future Work

The current model assumes a relatively static MANET topology during the seed selection phase. Future research could explore how high mobility (e.g., in Vehicular Social Networks) affects agent stability and whether dynamic re-selection of agents can be achieved without incurring even higher overhead.