Efficient Approaches to Top-r Influential Community Search

摘要

With the Internet of Things (IoT) gradually showing a trend of socialization, the community structure has been widely used in IoT applications, such as the smart home and smart city. Therefore, using the IoT and data mining technology to detect and analyze the relevant communities in the network is worth studying. In this article, we aim to identify the r most influential communities in a network, where an influential community is a cohesive subgraph with a considerable level of influence. In the literature, several efficient methods have been proposed to address this problem. These methods are all devised based on the assumption that nodes in the network are associated with different weights; in other words, every pair of nodes cannot have the same weight. Otherwise, these methods may retrieve imprecise results. However, nodes in a network may inevitably have the same weight in lots of real-world scenarios, such as mobile-edge computing networks. In this article, we are motivated to efficiently compute the top-r influential communities in a general case where nodes in the network may have arbitrary weights. To this end, we first proposed a unified search framework by improving the existing techniques. Then, we developed an efficient algorithm to judge the connectivity of nodes with the same weight, whose time complexity is linear to the size of the subgraph accessed by the algorithm. We conducted extensive performance studies on real data sets to demonstrate the effectiveness and efficiency of the proposed approaches.