/DynComm-R-package

Dynamic Network Community Detection - R Package

Primary LanguageHTMLGNU General Public License v2.0GPL-2.0

DynComm-R-package

Dynamic Network Communities Detection and Generation - R Package

Description

R package that implements several Algorithms used for evolving network analysis regarding community detection, using a common API.

Communities are calculated for the vertices and edges that change over time, without recalculating communities for the entire graph.

Algorithms use different, selectable, Criterion to evaluate the quality increase of the current community mapping.

Post-processing algorithms can be executed over the results to filter them for presentation without changing neither the graph nor the community mapping.

Features

Currently implemented features are:

  • Algorithms:

    • Dynamic Louvain Algorithm

  • Criterion

    • Classical Newman-Girvan, also called Modularity (Modularity)

  • Post-processing algorithms:

    • Community Density Optimization

Features planned to be added:

  • Algorithms:

    • TILES Community Detection [2]

    • RDyn generation module for dynamic networks [3]

  • Criterion:

    • Balanced Modularity (BalMod)

  • Post-processing algorithms:

    • Top N

    • Order by weight/edgeCount

  • Implement stand alone User Interfaces

Known bugs / limitations

Not being fixed in the current version

  • Edges that are not removed and calculations with differences in values: This is related to the way floating point numbers are subtracted in hardware and how numbers are represented in binary. When a number, like one third, that can not be completely represented in binary at a given number of bits (say 64 bit), is subtracted to another number, the result may deviate slightly from expected. When trying to hit exactly zero, like when removing edges, they may not be removed but linger with a very small value like 0.33X10^-17. The same happens when calculating weight aggregates, like the total weight of the graph, which influence the value of quality. These errors accumulate over time. A workaround is to snapshot the current graph and feed it to a new DynComm object. This is not being fixed in this version since it requires reimplementation of the graph object.

Project directory structure

The following are the most important files/directories to be aware in the root of the github project page:

  • DynComm_xxxxxx.xx.xxxx.tar.gz is the latest stable source code version of the package where xxxxxx.xx.xxxx are numbers indicating the version.

  • manual.pdf file contains the printer ready version of the description of the functions available in the User Interface with examples. This documentation might be outdated in comparison with the one available through the R help system.

  • LICENSE file describes the license agreement under which this project is shared.

  • CODE_OF_CONDUCT file describes behaviour restrictions that users submiting issues and contributors to this project must adhere to.

  • test directory contains small test networks.

  • oldReleases contains previous releases of the source code version of the package and are stored only for historical reasons. Never use these versions for current work.

  • R-CRAN is the root directory of the source code of this package.

  • CONTRIBUTING file contains guidelines that contributors to this project must adhere to.

  • dev is a directory with templates and documentation that might be useful for developers wishing to contribute to this project.

  • standalone is a directory with source code for stand alone versions of User Interfaces that allow to run parts of this project without R.

Software

To be able to use this package, the following software must be installed in your system, in the order presented. Search the web for more details on how to install and configure the software on your operating system, if required.

  • R-4.0.0

  • (optionally) RStudio 1.2.5042

Installation

The latest version of this package (201901.01.0004) was tested in Xubuntu 20.04 64 bit and Windows 7 Ultimate 64 bit.

You can install the stable version of this package from CRAN, if available, using the following command from within your R console:

install.packages("DynComm")

Otherwise, or to get the latest stable version, you need to compile the source code version provided in the directory named "R-CRAN" in the root of the project.

Additional steps for the source code version

Some additional software and configuration is required to compile and use the source code version of the package.

  • On Windows operating systems:

    • rtools40
    • Add rtools to the path. Check Rtools for details.

  • On Linux operating systems:

    • a C++11 compatible compiler and development libraries

Package Dependencies

The following packages are required to be installed from within R before trying to compile the source code version of the package. Some packages have dependencies of their own that may need fulfilling.

  • Rcpp (>= 0.12.15)

  • Rdpack

  • roxygen2

  • devtools

Compiling the source code version

The safest route is to download the latest stable source code version file from the root of this project and call the following command from within your R console, replacing the "x" by the correct version number:

install.packages("DynComm_xxxxxx.xx.xxxx.tar.gz", repos = NULL, type = "source")

To get the most recent version, which may not be stable nor functional, you can use the source code of the GitHub master version using the following command from within your R console:

devtools::install_github("softskillsgroup/DynComm-R-package/R-CRAN")

If you get errors about paths, directories or files using Staged Installation (the default), you might have to change "StagedInstall: yes" to "StagedInstall: no" in the DESCRIPTION file in order to be able to compile and install locally.

Documentation

Users please check either the manual.pdf file in this repository or the R help system for the latest version of the manual. Beware that documentation in the R help system might be more up to date. R help can be called using one of the following commands from R console.

help("DyComm-package") or ??"DyComm-package"

Developers please refer to the developer documentation in the R help system using one of the following commands from R console.

help("DyComm-package-dev") or ??"DyComm-package-dev"

Contributing

Please read the CONTRIBUTING file.

License

This project is shared under GNU GPL version 2 or later. Please read the LICENSE file for more details.

Referenced Work

This package uses the following work as reference material for the implementation of the algorithms.

  • [1]:

    • Title: Dynamic community detection in evolving networks using locality modularity optimization
    • Author: Cordeiro, Mário and Sarmento, Rui Portocarrero and Gama, João
    • Journal: Social Network Analysis and Mining
    • Date: 2016
    • Volume: 6
    • Number: 1
    • Pages: 1--20
    • Publisher: Springer Vienna

  • [2]:

    • Title: Tiles: An Online Algorithm for Community Discovery in Dynamic Social Networks
    • Author: Rossetti, Giulio and Pappalardo, Luca and Pedreschi, Dino and Giannotti, Fosca
    • Journal: Mach. Learn.
    • Date: August 2017
    • Volume: 106
    • Number: 8
    • ISSN: 0885-6125
    • Pages: 1213--1241
    • URL: https://doi.org/10.1007/s10994-016-5582-8
    • DOI: 10.1007/s10994-016-5582-8
    • ACMID: 3128003
    • Publisher: Kluwer Academic Publishers
    • Address: Hingham, MA, USA

  • [3]:

  • [4]:

    • Title: Density-based Community Detection/Optimization
    • Author: Sarmento, Rui Portocarrero
    • Journal: arXiv
    • Date: Apr 2019
    • Eprint: 1904.12593
    • URL: https://arxiv.org/abs/1904.12593