Evaluating regrets while joining a community - A Novel Community Detection in Large Networks using Game Theory.

This is done as part of my Bachelor’s thesis under Prof. Susanta Chakraborty.

Attached paper accepted at AAAI MLOR 2021.

Would I regret later joining this Community ? Using temporal neighborhood information for community retention in a game theoretic community detection framework

Table of Contents

• Features
• Demo
• Customization
• Citation

Features

• Faster convergence than existing game-theoretic based approaches, maintaining the same community structure.
• Proposal of a novel modularity maximization objective that takes into account community retention, resulting in faster convergence.
• Theoretical Gaurantees on Nash equilibria for proposed modularity-maximization metric.
• Real world effectivness. Experimented on datasets
  • Amazon
  • Enron
  • Karate
  • Football
  • Dolphin
  • ERDOS992
  • fb pages food
  • retweet network
  • fb pages politician

Demo

If you want to run a demo of our code, you can follow the following steps:

Windows / Ubuntu

Via Visual Studio Code

• Open Visual Studio Code
• git clone https://github.com/prateekiiest/btech_thesis.git
• Follow setup of Jupyter Notebooks in Visual Studio Code from this setup tutorial
• Once you have cloned the repository do cd btech-thesis/code
• Open comm-regret.ipynb in your Jupyter Kernel.

Via Anaconda

• Install Anaconda following this documentation - Windows Install , Linux Install
• git clone https://github.com/prateekiiest/btech_thesis.git under your specified designated folder path.
• Open Jupyter Notebook (anaconda installation comes with all features including Jupyter notebook/ Spyder IDE)
• Once the notebook folder view opens, navigate to btech-thesis/code
• Open comm-regret.ipynb in your Jupyter Kernel.

Customization

The main code is handled by the communityDetect function defined in code. It takes the following parameters in the order given

• array of community labels (each node is initialized with a unique community label initially)
• graph structure (consisting of nodes and edges, we use a Networkx Data structure)
• nIter (no. of iterations to run)
• Lambda (the degree of community retention, lower the value - higher chances of nodes being retained in the same community they previosly chose)

Here nIter and Lambda can be customized w.r.t different graph datasets.

Datasets used

Stanford Graph Dataset

Citation

If you use this code for your research, please consider citing the arXiv preprint

@article{chanda2021would,
  title={Would I regret later joining this Community? Using temporal neighborhood information for community retention in a game theoretic community detection framework},
  author={Chanda, Prateek and Chakraborty, Susanta},
  booktitle={AAAI-22 Workshop on Machine Learning for Operations Research},
  year={2021}
}