3 years ago

Non-Parametric Detection of Network Communities; The Natural Way; A Cascaded Stackelberg Game.

Nishant Deepak Keni

Real-World networks have an inherently dynamic structure and are often composed of communities that are constantly changing in membership. Identifying these communities is of great importance when analyzing structural properties of networks. Hence, recent years have witnessed intense research in of solving the challenging problem of detecting such evolving communities. The mainstream approach towards community detection involves optimization of a global partition quality metric (e.g. modularity) over the network. Another technique, Spectral Clustering, involves mapping of original data points in a lower dimensional space, where the clustering properties of a graph are much more evident, and then applying standard clustering techniques for identifying communities. However, the traditional spectral clustering techniques cannot naturally learn the number of communities in networks. These techniques are based on external community connectivity properties, and often fail to identify smaller community structures in dense networks. In this article, we propose an algorithm, namely, the Cascaded Stackelberg Community Detection Algorithm (CASCODE) inspired by the Stackelberg Duopoly Game. This algorithm uses the notion of a leader-follower relationship between the nodes to influence the actions of either. The intuition of the algorithm is based on the natural expected internal structure in evolving communities in networks. Thus, the algorithm is able to naturally learn the number of communities in a network in contrast with other techniques such as Spectral Clustering, which require the expected number of communities as an input. Because this Stackelberg Model-based Community Detection algorithm detects communities through their internal structure, we are able to obtain a finer community structure resolution in dense networks.

Publisher URL: http://arxiv.org/abs/1801.06208

DOI: arXiv:1801.06208v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.