Skip to content

Instantly share code, notes, and snippets.

@dkgoutham

dkgoutham/report.md

Last active August 27, 2023 14:53
Show Gist options
  • Save dkgoutham/f5c0364ceaa241a26774ded3a34ce54f to your computer and use it in GitHub Desktop.
Save dkgoutham/f5c0364ceaa241a26774ded3a34ce54f to your computer and use it in GitHub Desktop.
Download ZIP
Complex Networks Library for Pharo - GSoC 2023 Final Report
Raw
report.md

Complex Networks Library for Pharo - GSoC 2023 Final Report

Introduction:

Hello! I am Goutham, a fourth-year student majoring in Mathematics and Computing at IIT Guwahati, India. This summer, I had the privilege to be part of the Google Summer of Code (GSoC) program, where I worked with the Pharo Consortium. My primary project revolved around developing a Complex Networks library, and I was fortunate to be mentored by Gordana Rakic and Sebastian Jordan.

Goals of the Project:

The aim of this project was to develop a robust and versatile Complex Networks library for Pharo. The library was envisioned to cater to both basic and advanced needs, ranging from creating nodes and edges to implementing sophisticated network algorithms. By providing these functionalities, the library would serve as a one-stop solution for all network analysis needs in Pharo.

What I Did:

  1. Network Components: Implemented foundational classes that serve as the building blocks for any network. These include:

    • NetworkNode: Represents individual nodes in a graph, each with a unique ID and associated attributes.
    • NetworkUndirectedEdge: Represents edges without any direction, connecting two nodes.
    • NetworkDirectedEdge: Represents directed edges connecting a source node to a target node.
    • NetworkAttribute: Provides the ability to associate attributes with nodes or edges.
    • NetworkGraph: Central class to build, modify, and query the entire graph.

  2. Network Algorithms: Developed a wide array of algorithms essential for network analysis. These algorithms allow users to measure, analyze, and gain insights into the structure and properties of networks. The detailed list of implemented algorithms includes:

    • Assortativity: The Assortativity class provides methods to measure the assortativity of networks. Assortativity quantifies the similarity of connections in the graph with respect to node degree.
    • Centrality: The Centrality class contains various methods to compute centrality measures of a graph. These measures help identify the importance of nodes within the graph.
    • Triangles: The Triangles class offers methods to analyze triangles in a graph. Triangles are sets of three nodes that are all connected to each other.
    • Clustering Coefficient: The ClusteringCoefficient class provides methods to compute the clustering coefficient of nodes in a network. This coefficient helps understand the local structure of the network.
    • Efficiency: The Efficiency class calculates the efficiency of a network. Efficiency quantifies the inverse of the average shortest path length in the network. It analyzes how effectively information can be exchanged over the network.
    • Distance Measure: The DistanceMeasures class offers methods to compute various distance-related properties of a graph, such as eccentricity, diameter, radius, and more.
    • Cliques: The Cliques class implements the Bron-Kerbosch algorithm with a pivot to identify all maximal cliques in an undirected graph. It detects tight-knit communities by identifying all cliques in the network.
    • Matrices: The Matrices class provides methods for creating and manipulating matrices representing different aspects of a graph.
    • Louvian Community Detection:The LouvainCommunityDetection class provides methods to detect communities within a graph using the Louvain Community Detection algorithm. It is a heuristic method for detecting communities in large networks.
    • Shortest Path: The ShortestPaths class contains algorithms to compute the shortest paths in a graph.
    • Bridges and Articulation: The BridgesAndArticulation class provides methods to detect bridges and articulation points in undirected graphs.

  3. Random Graph Generator: The ConfigurationModel class provides methods to create random graphs using a given degree sequence.

Relevant Links:

Current State:

The library is in a functional state with a comprehensive suite of network components and algorithms. The implemented features were demonstrated through a video tutorial, which provides an overview and showcases their applications. This library has the potential to be a valuable tool for researchers, developers, and students working with network analysis in Pharo.

What's Left to Do:

While the library is comprehensive, there is always room for enhancement. The following are some areas of further development:

  • Tests: Writing tests for some classes to ensure the robustness and correctness of the implemented functionalities.
  • Additional Network Algorithms: Introduce more algorithms like Network Flow, Maximum Matching, Graph Coloring, and Hamiltonian Cycles.

Challenges & Learnings:

This project was both challenging and enlightening. Working on a library that caters to such a vast domain had its hurdles. Understanding the intricacies of network analysis, ensuring that the algorithms were efficient, and making the library user-friendly were some of the challenges I encountered. Through these challenges, I learned the importance of thorough research, iterative testing, and seeking feedback. Collaborating with the Pharo community and my mentors, Gordana Rakic and Sebastian Jordan, enriched my understanding and honed my skills. It was a summer of immense growth and learning.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment