An autonomy-oriented computing approach to community mining in distributed and dynamic networks

摘要

A network community refers to a special type of network structure that contains a group of nodes connected based on certain relationships or similar properties. Our ability to mine communities hidden inside networks will readily enable us to effectively understand and exploit such networks. So far, various methods and algorithms have been developed to perform the task of community mining, where it is often required that the networks are processed in a centralized manner, and their structures will not dynamically change. However, in the real world, many applications involve distributed and dynamically evolving networks, in which resources and controls are not only decentralized but also updated frequently. It would be difficult for the existing methods to deal with these types of networks since their global topological representations are either not available or too hard to obtain due to their huge size, decentralization, and/or dynamic updates. The aim of our work is to address the problem of mining communities from a distributed and dynamic network. It differs from the previous ones in that here we introduce the notion of self-organizing agent networks, and provide an autonomy-oriented computing (AOC) approach to distributed and incremental mining of network communities. The AOC-based method utilizes reactive agents that can collectively detect and update community structures in a distributed and dynamically evolving network, based only on their local views and interactions. While providing detailed formulations, we present the results of our systematic validations using real-world benchmark networks as well as synthetic networks that include a distributed intelligent Portable Digital Assistant (iPDA) network example.