Skip to content

Latest commit

 

History

History
736 lines (536 loc) · 35.8 KB

README.md

File metadata and controls

736 lines (536 loc) · 35.8 KB
Raw

Complex Networks Library

Welcome to the Complex Networks Library, a comprehensive suite designed to model, analyze, and visualize complex networks using object-oriented paradigms. Built with elegance and flexibility in mind, this library offers a rich set of classes and methods catering to various needs in network science.

Overview

Networks are everywhere - from social networks that connect people to biological systems connecting various species in an ecosystem. Understanding their structure, dynamics, and intricacies can provide valuable insights into diverse fields such as sociology, biology, physics, and computer science. The Complex Networks Library is developed to be a one-stop solution for researchers, developers, and enthusiasts who are keen to dive deep into the world of networks.

Key Features:

  1. Versatile Network Components: The core of the library consists of classes like NetworkGraph, NetworkNode, NetworkDirectedEdge, NetworkUndirectedEdge, and NetworkAttribute, ensuring a robust representation of nodes, edges, and their attributes.

  2. Algorithms and Analysis: Whether it's finding the centrality using methods from the Centrality class or analyzing matrix representations with the Matrices class, the library covers a broad spectrum of graph algorithms and network metrics.

  3. Graph Generation: Classes like ConfigurationModel allow users to create complex network models from given degree sequences, aiding in generating both directed and undirected graphs.

  4. Extensible Design: With its modular architecture, adding new algorithms, network models, or features becomes a seamless process.

Getting Started

Dive into the individual classes' documentation to understand their functionalities and see usage examples. Whether you're building a new kind of network model, analyzing existing networks, or simply exploring the fascinating world of graphs, the Complex Networks Library provides the tools you need.

NetworkNode

A class to represent a network node within a graph.

Instance Variables

  • id: A unique identifier for the node.
  • adjacentNodes: A collection of nodes adjacent to this node.
  • adjacentEdges: A collection of edges adjacent to this node.
  • attributes: A collection of attributes associated with this node.

Methods

Instance Creation

  • with: anId: Creates a new node with the specified identifier anId.

Adding

  • addAttribute: anAttributeObject: Adds an attribute to the node.

Accessing

  • adjacentEdges: Returns the adjacent edges to this node.
  • adjacentEdges: aEdgeList: Sets the adjacent edges to this node.
  • adjacentNodes: Returns the adjacent nodes to this node.
  • adjacentNodes: aNodeList: Sets the adjacent nodes to this node.
  • from: sourceNode: A placeholder method for derived classes.
  • from: sourceNode edge: anEdge: A placeholder method for derived classes.
  • id: Returns the identifier of the node.
  • id: anId: Sets the identifier of the node.
  • to: targetNode: Adds an adjacent node.
  • to: targetNode edge: anEdge: Adds an adjacent node and edge.

Initialization

  • initialize: Initializes the instance variables.

Printing

  • printOn: stream: Prints the node's label and identifier on the given stream.

Label

  • label: Returns a string representing the label of the node.

Usage Example

node := NetworkNode with: 1.

NetworkUndirectedEdge

A class to represent an undirected edge in the network.

Instance Variables

  • model: A reference to the associated model object.
  • node1: One of the nodes connected by the edge.
  • node2: The other node connected by the edge.
  • attributes: A collection of attributes associated with the edge.

Methods

Adding

  • addAttribute: anAttributeObject: Adds an attribute to the edge.

Accessing

  • asTuple: Returns a tuple containing the connected nodes.
  • model: Returns the associated model object.
  • model: anObject: Sets the associated model object.
  • node1: Returns one of the connected nodes.
  • node1: anObject: Sets one of the connected nodes.
  • node2: Returns the other connected node.
  • node2: anObject: Sets the other connected node.

Initialization

  • initialize: Initializes the instance variables.

Printing

  • printOn: aStream: Prints the edge's connected nodes on the given stream.

Usage Example

edge := NetworkUndirectedEdge new.
edge node1: node1.
edge node2: node2.

NetworkDirectedEdge

This class represents a directed edge in the network, extending from one node (source) to another (target).

Instance Variables

  • model: A reference to the associated model object.
  • from: The source node of the edge.
  • to: The target node of the edge.
  • attributes: A collection of attributes associated with the edge.

Methods

Adding

  • addAttribute: anAttributeObject: Adds an attribute to the edge.

Converting

  • asTuple: Returns a tuple containing the source and target nodes.

Accessing

  • from: Returns the source node of the edge.
  • from: anObject: Sets the source node of the edge.
  • model: Returns the associated model object.
  • model: anObject: Sets the associated model object.
  • to: Returns the target node of the edge.
  • to: anObject: Sets the target node of the edge.

Initialization

  • initialize: Initializes the instance variables.

Printing

  • printOn: aStream: Prints the edge's source and target nodes on the given stream.

Usage Example

edge := NetworkDirectedEdge new.
edge from: node1.
edge to: node2.

NetworkAttribute

A class to represent a node's or edge's attribute within the network.

Instance Variables

  • model: A reference to the associated model object.
  • attributeName: The name of the attribute.
  • attributeValue: The value of the attribute.

Methods

Getter

  • attributeName: Returns the name of the attribute.
  • attributeValue: Returns the value of the attribute.

Setter

  • attributeName: aString: Sets the name of the attribute.
  • attributeValue: aString: Sets the value of the attribute.

Initialization

  • setAttribute: name value: value: Initializes the attribute with a given name and value.

Usage Example

attribute := NetworkAttribute new.
attribute setAttribute: 'color' value: 'red'.

NetworkGraph

A class that represents a network graph, containing methods for building and manipulating the graph.

Instance Variables

  • nodes: A collection of nodes in the graph.
  • edges: A collection of edges in the graph.
  • sortingBlock: A block used for sorting nodes.
  • directed: A boolean indicating whether the graph is directed or not.

Methods

Testing

  • isAbstract: Returns whether the class is abstract.

Adding

  • addDirectedEdge: fromId to: toId: Adds a directed edge between nodes with given IDs.
  • addUndirectedEdge: fromId to: toId: Adds an undirected edge between nodes with given IDs.

Building - Graph

  • addNodeByID: anId: Adds a node with the given ID to the graph.
  • edges: aCollection from: source to: target: Adds edges to the graph from a collection, specifying source and target.
  • emptyGraph: Empties the graph.
  • nodes: aNodeList: Adds nodes from a list to the graph.
  • rawNodes: aRawNodeList: Sets the nodes from a raw node list.

Accessing

  • directed: Returns whether the graph is directed.
  • directed: aBoolean: Sets whether the graph is directed.
  • edgeBetween: node1 and: node2: Returns the edge between two nodes, if exists.
  • edgeClass: Returns the appropriate edge class based on the graph's directedness.
  • edges: Returns the edges in the graph.
  • findEdge: aModel: Finds an edge by its model.
  • findNode: anId: Finds a node by its ID.
  • findNode: anId ifAbsent: aBlock: Finds a node by its ID, executing a block if absent.
  • findNode: anId ifFound: aBlock: Finds a node by its ID, executing a block if found.
  • getAttributeWithName: anAttributeName edge: anEdge: Gets an attribute by name from an edge.
  • graph: Returns the graph as a collection of nodes and edges.
  • nodeClass: Returns the node class.
  • nodes: Returns the nodes in the graph.

Configuration

  • initialize: Initializes the instance variables.

Usage Example

graph := NetworkGraph new.
graph addNodeByID: 1.
graph addNodeByID: 2.
graph addDirectedEdge: 1 to: 2.

Network Algorithms

Assortativity

The Assortativity class contains methods to measure the assortativity of networks. Assortativity quantifies the similarity of connections in the graph with respect to the node degree. A positive assortativity coefficient indicates that nodes tend to link to other nodes with the same or similar degree, while a negative coefficient indicates nodes tend to link to nodes with differing degrees.

Methods:

1. assortativityCoefficientFor: aGraph

  • Description: Computes the assortativity coefficient for an undirected graph.
  • Formula: $$ r = \frac{4 \times E \times \sum_{ij} e_{ij} - \left(\sum_{i} a_{i} + b_{i}\right)^2}{2 \times E \times \sum_{i} a_{i}^2 + b_{i}^2 - \left(\sum_{i} a_{i} + b_{i}\right)^2} $$ Where $E$ is the number of edges and $e_{ij}$, $a_{i}$, and $b_{i}$ are derived from the degrees of nodes connected by each edge.

2. assortativityCoefficientFor: aGraph useInDegree: useInDegree useOutDegree: useOutDegree

  • Description: Computes the assortativity coefficient for a directed graph considering in-degrees, out-degrees, or both.
  • Formula: $$ r = \frac{\sum_{ij} e_{ij} - \left(\sum_{i} a_{i} + b_{i}\right)^2}{\sum_{i} a_{i}^2 + b_{i}^2 - \left(\sum_{i} a_{i} + b_{i}\right)^2} $$ Where $e_{ij}$, $a_{i}$, and $b_{i}$ are derived from the in-degrees and out-degrees of nodes connected by each edge.

3. averageNeighborDegree: aGraph

  • Description: Computes the average degree of the neighbors for each node in the graph.

4. totalNeighborDegrees: aGraph

  • Description: Computes the total degree of the neighbors for each node in the graph.

5. totalNeighbors: aGraph

  • Description: Computes the total number of neighbors for each node in the graph.

Conclusion:

Assortativity is a crucial measure to understand the tendency of nodes to connect with other nodes of similar degree in a network. The Assortativity class offers comprehensive methods to calculate this metric, providing deeper insights into the structure and behavior of complex networks.

Centrality

The Centrality class offers a collection of methods to compute various centrality measures of a graph. These measures provide insights into the relative importance of nodes within the graph.

Methods:

1. betweennessCentrality: aGraph

  • Description: Calculates the betweenness centrality for each node in the graph. A node's betweenness centrality reflects the amount of times it acts as a bridge along the shortest path between two other nodes.
  • Formula: $$ g(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}} $$ where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma_{st}(v)$ is the number of those paths that pass through $v$.

2. closenessCentrality: aGraph

  • Description: Determines the closeness centrality for each node, which measures how close a node is to all other nodes in the graph.
  • Formula: $$ C(x) = \frac{1}{\sum_{y} d(y, x)} $$ where $d(y, x)$ is the shortest distance between nodes $y$ and $x$.

3. degreeCentrality: aGraph

  • Description: Calculates the degree centrality for each node in the graph. A node's degree centrality is its degree (number of adjacent nodes) divided by the maximum possible degree in the graph (n-1).
  • Formula: $$ C_D(v) = \frac{deg(v)}{n-1} $$ where $deg(v)$ is the degree of node $v$ and $n$ is the total number of nodes.

4. inDegreeCentrality: aGraph

  • Description: Computes the in-degree centrality for each node in a directed graph, which is the number of incoming edges for each node.
  • Formula: $$ C_{in}(v) = \frac{incoming(v)}{n-1} $$ where $incoming(v)$ is the number of incoming edges to node $v$.

5. inOutDegreeCentrality: aGraph

  • Description: Calculates both the in-degree and out-degree centrality for each node in a directed graph.
  • Formulas:
    • In-degree centrality: $C_{in}(v) = \frac{incoming(v)}{n-1}$
    • Out-degree centrality: $C_{out}(v) = \frac{outgoing(v)}{n-1}$

6. outDegreeCentrality: aGraph

  • Description: Computes the out-degree centrality for each node in a directed graph, which is the number of outgoing edges for each node.
  • Formula: $$ C_{out}(v) = \frac{outgoing(v)}{n-1} $$ where $outgoing(v)$ is the number of outgoing edges from node $v$.

Helper Methods:

These methods are not directly related to calculating a specific centrality but aid in the calculations:

  • bfsFrom: startNode withDistances: distances: Performs a breadth-first search from a given node to calculate distances.
  • calculateBetweennessFor: node storingIn: betweenness graph: aGraph: Uses both BFS and DFS to compute betweenness centrality for a given node.
  • performBFSFrom: node distances: distances predecessors: predecessors sigma: sigma queue: queue stack: stack: Executes BFS for calculating shortest paths.
  • performDFSFor: node stack: stack sigma: sigma delta: delta predecessors: predecessors betweenness: betweenness: Executes DFS to accumulate betweenness values.

Conclusion:

Centrality measures are essential in understanding the importance and influence of nodes within a network. The Centrality class provides a comprehensive set of methods to compute these measures, assisting in the deep analysis of complex networks.

Triangles

The Triangles class offers methods to analyze triangles in a graph. Triangles are three nodes that are all connected to each other. Analyzing triangles is important in understanding the clustering and transitivity of a network.

Methods

1. trianglesFor: aGraph

  • Description: Counts the total number of triangles in the given graph.
  • Formula: A triangle is formed by three nodes $A, B, C$ such that $A \leftrightarrow B, B \leftrightarrow C, C \leftrightarrow A$. This method iterates through all possible node combinations and checks for these connections.
  • Usage: Useful for analyzing the overall clustering in the graph, which can indicate community structures or resilience in a network.

2. trianglesFor: node in: aGraph

  • Description: Counts the number of triangles that include a specific node in the given graph.
  • Formula: Similar to the global triangle count but focuses on triangles that include a specific node. It iterates through the adjacent nodes of the given node and counts triangles.
  • Usage: Useful for understanding the local clustering around a particular node.

3. trianglesWithMatrixFor: aGraph

  • Description: Counts the total number of triangles in the given graph using matrix multiplication.
  • Formula: A triangle count can be obtained by calculating the trace of the cube of the adjacency matrix ($\text{trace}(A^3)/6$, where $A$ is the adjacency matrix). The division by 6 accounts for each triangle being counted six times.
  • Usage: Provides an efficient matrix-based method to count triangles, especially in large dense graphs.

4. trianglesWithVectorFor: aGraph

  • Description: Counts the total number of triangles in the given graph using vector operations.
  • Formula: Similar to matrix-based calculation, but uses vector operations to reduce computational complexity.
  • Usage: Another efficient way to count triangles, particularly suitable for large sparse graphs.

Conclusion

The Triangles class provides various methods to analyze triangles in a graph, both globally and for specific nodes. These methods offer insights into the clustering and community structure of the graph. By offering different algorithms (iterative, matrix-based, vector-based), it allows flexibility in handling different sizes and types of graphs.

Clustering Coefficient

The ClusteringCoefficient class offers methods to compute the clustering coefficient of nodes in a network. The clustering coefficient quantifies how close the neighbors of a node are to being a clique (i.e., all neighbors are connected to one another). This measure provides insights into the local structure and potential for information or error propagation in the network.

Methods:

1. clusteringFor: aGraph

  • Description: This is a wrapper method that computes the clustering coefficient for all nodes in the graph. Depending on whether the graph is directed or undirected, it calls the appropriate method (directedClusteringFor: or undirectedClusteringFor:) to compute the clustering coefficient.

2. directedClusteringFor: node in: aGraph

  • Description: Calculates the clustering coefficient for a node in a directed graph.
  • Formula: $$ C(v) = \frac{T(v)}{k_{in}(v) \times k_{out}(v)} $$ Where:
    • $T(v)$ is the number of triangles connected to node $v$, determined using the utility method countTrianglesFor:.
    • $k_{in}(v)$ is the in-degree and $k_{out}(v)$ is the out-degree of $v$.

3. undirectedClusteringFor: node in: aGraph

  • Description: Computes the clustering coefficient for a node in an undirected graph.
  • Formula: $$ C(v) = \frac{2T(v)}{k(v)(k(v)-1)} $$ Where:
    • $T(v)$ is the number of triangles connected to node $v$, determined using the utility method countTrianglesFor:.
    • $k(v)$ is the degree of $v$.

Utility Methods:

countTrianglesFor: node in: aGraph

  • Description: A utility method that determines the number of triangles connected to a given node in the graph. A triangle is a set of three nodes that are all connected to one another. This method is utilized in the above two methods to compute the number of triangles for a given node.

Conclusion:

The clustering coefficient is a crucial metric in understanding the local connectedness or clustering of nodes within a network. The ClusteringCoefficient class offers a comprehensive set of methods to compute this measure, enabling in-depth analysis of complex networks.

Efficiency

The Efficiency class is designed to calculate the efficiency of a network based on various measures. This class is an implementation of the network efficiency measures as described in the paper PhysRevLett.87.198701.

Definitions:

  • Efficiency: It quantifies the inverse of the average shortest path length in the network. Higher efficiency indicates a more compact network.

Methods:

1. efficiencyBetween: node1 and: node2 in: aGraph

  • Purpose: Calculate the efficiency between a pair of nodes in the graph.
  • Parameters:
    • node1, node2: The two nodes between which the efficiency is to be calculated.
    • aGraph: The graph containing the nodes.
  • Formula: $$ E = \frac{1}{\text{distance} + 1} $$
  • Description: This method first calculates the shortest distance between the two nodes using the ShortestPaths class. The efficiency is then calculated using the formula.

2. globalEfficiencyIn: aGraph

  • Purpose: Calculate the global efficiency of an undirected graph.
  • Parameters:
    • aGraph: The graph for which the global efficiency is to be calculated.
  • Description: This method sums the efficiencies between all pairs of distinct nodes in the graph and then averages them. The global efficiency gives an idea of the overall efficiency of the entire graph.

3. localEfficiencyIn: aGraph

  • Purpose: Calculate the local efficiency of an undirected graph.
  • Parameters:
    • aGraph: The graph for which the local efficiency is to be calculated.
  • Description: This method calculates the efficiency for each node based on its neighbors. The local efficiency gives an idea of how efficiently information is exchanged in the neighborhood of each node.

Conclusion:

The Efficiency class provides a comprehensive toolset for analyzing the efficiency of a network. By measuring both local and global efficiencies, it offers insights into how information flows through the network and how network topology affects this flow.

Distance Measures

The DistanceMeasures class provides a suite of methods to compute various distance-related properties of a graph, such as eccentricity, diameter, radius, and more.

Methods:

1. barycenterOf: aGraph

  • Purpose: Find the barycenter nodes of the graph. A barycenter node is a node that has the minimum sum of distances to all other nodes in the graph.
  • Return: List of nodes that are barycenters of the graph.
  • Note: Utilizes the utility method distancesFrom: startNode in: aGraph to compute distances.

2. centerOf: aGraph

  • Purpose: Identify the center nodes of the graph. These are nodes whose eccentricity equals the radius of the graph.
  • Return: List of nodes that are center nodes.

3. diameterOf: aGraph

  • Purpose: Calculate the diameter of the graph. The diameter is the maximum eccentricity among all nodes in the graph.
  • Return: Diameter value.

4. findEccentricity: aGraph node: aNode

  • Purpose: Determine the eccentricity of a given node in the graph. Eccentricity is the greatest distance between the node and any other node.
  • Return: Eccentricity value.

5. findEccentricityAll: aGraph

  • Purpose: Compute the eccentricity for all nodes in the graph.
  • Return: List of eccentricities.

6. findEccentricityById: aGraph id: anId

  • Purpose: Get the eccentricity of a node specified by its ID.
  • Return: Eccentricity value.

7. peripheryOf: aGraph

  • Purpose: Identify the periphery nodes of the graph. These are nodes whose eccentricity equals the diameter of the graph.
  • Return: List of nodes that are periphery nodes.

8. radiusOf: aGraph

  • Purpose: Calculate the radius of the graph. The radius is the minimum eccentricity among all nodes in the graph.
  • Return: Radius value.

Utility Methods:

  • distancesFrom: startNode in: aGraph: This utility method computes the shortest distances from a given start node to all other nodes in the graph using Breadth-First Search (BFS). It is utilized within the barycenterOf: aGraph method.

Conclusion:

The DistanceMeasures class offers a comprehensive set of methods to analyze various distance-related properties of a graph. Understanding these properties is crucial for graph analysis, providing insights into the structure and connectivity of the network.

Cliques

The Cliques class is an implementation of the Bron-Kerbosch algorithm with a pivot. This algorithm is used to identify all maximal cliques in an undirected graph.

Definitions

  • Clique: A subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent.
  • Maximal Clique: A clique that cannot be extended by adding an adjacent vertex. In other words, a clique which does not exist as a proper subset of any other clique.

Main Methods

1. bronKerbosch: r candidateSet: p exclusionSet: x

  • Purpose: Implements the Bron-Kerbosch algorithm to find maximal cliques.
  • Parameters:
    • r: Current clique.
    • p: Candidate set of vertices that can be added to the current clique.
    • x: Exclusion set of vertices that are excluded from being added to the current clique.

The method works by:

  1. Checking if both the candidate set p and exclusion set x are empty. If true, r is a maximal clique.
  2. Choosing a pivot vertex from the union of p and x.
  3. Iterating over the vertices in p not adjacent to the pivot vertex. For each vertex, it updates r, p, and x and makes a recursive call.

2. initialize

  • Purpose: Constructor for the Cliques object.
  • How: Initializes the maximalCliques collection which will store all the found maximal cliques.

3. runBronKerbosch: aGraph

  • Purpose: Entry point for running the Bron-Kerbosch algorithm.
  • Parameters:
    • aGraph: The graph to find maximal cliques in.

The method initializes the algorithm with:

  • An empty current clique r.
  • All nodes of the graph as the candidate set p.
  • An empty exclusion set x.

4. storeClique: aClique

  • Purpose: Stores a found maximal clique.
  • Parameters:
    • aClique: The clique to be stored.

The method adds the clique to the maximalCliques collection.

Conclusion

The Cliques class provides a clear and efficient implementation of the Bron-Kerbosch algorithm for finding all maximal cliques in an undirected graph. The use of a pivot in the algorithm optimizes the number of recursive calls, improving efficiency.

Matrices

The Matrices class provides a collection of methods for creating and manipulating various matrices that represent different aspects of a graph. These matrices are central to numerous graph algorithms and analyses.

Methods

1. adjacencyMatrixFor: aGraph

  • Description: Constructs the adjacency matrix for the given graph.
  • Formula: The adjacency matrix $A$ has elements $A_{ij} = 1$ if there is an edge between nodes $i$ and $j$, and $A_{ij} = 0$ otherwise.
  • Usage: Represents the connections between nodes in a graph.

2. algebraicConnectivityFor: aGraph

  • Description: Computes the algebraic connectivity of the graph, which is the second smallest eigenvalue of the Laplacian matrix.
  • Formula: If $\lambda$ is the set of eigenvalues of the Laplacian matrix, then the algebraic connectivity is $\lambda_2$.
  • Usage: Gives insights into the connectivity and robustness of the graph.

3. attrMatrixFor: aGraph

  • Description: Constructs a matrix representing the attributes of the nodes in the graph.
  • Usage: Encodes node attributes as a matrix, where rows correspond to nodes and columns to attributes.

4. incidenceMatrixFor: aGraph

  • Description: Constructs the incidence matrix for the given graph.
  • Formula: For directed graphs, $B_{ij} = -1$ if node $i$ is the tail of edge $j$, $B_{ij} = 1$ if node $i$ is the head of edge $j$, and $B_{ij} = 0$ otherwise. For undirected graphs, $B_{ij} = 1$ if edge $j$ is incident to node $i$, and $B_{ij} = 0$ otherwise.
  • Usage: Represents relationships between nodes and edges in a graph.

5. laplacianMatrixFor: aGraph

  • Description: Constructs the Laplacian matrix for the given graph.
  • Formula: The Laplacian matrix $L$ is given by $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix.
  • Usage: Used in spectral clustering and other graph algorithms.

6. modularityMatrixFor: aGraph

  • Description: Constructs the modularity matrix for the given graph.
  • Formula: $$ B = A - \frac{d_i \cdot d_j}{2m} $$ where $A$ is the adjacency matrix, $d_i$ and $d_j$ are the degrees of nodes $i$ and $j$, and $m$ is the total number of edges in the graph.
  • Usage: Used in community detection algorithms to optimize the modularity of a partition.

Conclusion

The Matrices class provides key functionalities for representing and analyzing graphs through matrices. By encapsulating complex mathematical operations, it allows for straightforward application in various graph algorithms.

Note: The PMMatrix class from the vector-matrix library is used for matrix manipulations.

Louvain Community Detection

The LouvainCommunityDetection class provides methods to detect communities within a given graph using the Louvain Community Detection algorithm. The algorithm is a heuristic method that aims to optimize the modularity of the partition of the graph.

Main Methods:

1. detectCommunities

  • Description: Detect communities within the graph by iteratively calling phaseOne and phaseTwo until communities are stabilized.
  • Usage: This method is called to initiate the community detection process.

2. detectCommunities: aGraph

  • Description: A utility function to detect communities within a given graph.
  • Usage: Creates an instance of the class, initializes with the provided graph, and then detects communities.

Algorithm Components:

1. modularityGainFor: node movingTo: community

  • Description: Calculates the modularity gain when a node is moved to a different community.
  • Formula: $$ \text{gain} = \sum_{\text{other nodes}} \left( \text{modularityMatrix}( \text{currentCommunity}, \text{otherCommunity} ) - \text{modularityMatrix}( \text{existingCommunity}, \text{otherCommunity} ) \right) $$

2. phaseOne

  • Description: Iteratively relocates nodes to maximize modularity until there's no improvement.
  • Usage: Used in the detectCommunities method.

3. phaseTwo

  • Description: Aggregates nodes into communities and builds a new aggregate graph for the next level.
  • Usage: Used in the detectCommunities method.

Construction Methods:

1. createCoarseGrainedGraph: aGraph using: communities

  • Description: Constructs a coarse-grained version of the input graph based on the identified communities.
  • Usage: Used in phaseTwo to create a higher-level representation of the input graph based on the communities detected.

2. createCommunityEdges: communities

  • Description: Constructs edges for the coarse-grained graph based on the community structure detected.
  • Usage: Each edge in the coarse-grained graph represents connections between communities.

3. createCommunityNodes: communities

  • Description: Constructs node representations for each detected community.
  • Usage: Each node in the coarse-grained graph represents a community from the input graph.

Initialization Methods:

  1. initializeCommunities: Initializes each node in the graph to its own community.
  2. initializeWithGraph: aGraph: Initializes the algorithm with a given graph and prepares necessary data structures.

Conclusion:

The LouvainCommunityDetection class offers a precise algorithm for detecting communities within a given graph, aiming to optimize the modularity of the partition. By leveraging both local and global optimization, it can uncover hierarchical community structures within complex networks.

Shortest Paths

The ShortestPaths class provides a set of algorithms to compute and analyze the shortest paths in a graph. These algorithms are fundamental in network analysis and have various applications in routing, social networks, and other domains.

Methods

1. allShortestPathsIn: aGraph

  • Description: Computes all pairwise shortest paths in the given graph.
  • Usage: Useful for computing and storing all the shortest paths for quick access in subsequent computations.

2. floydWarshallFor: aGraph

  • Description: Implements the Floyd-Warshall algorithm to compute all pairs of shortest paths in the given graph.
  • Formula: The algorithm uses dynamic programming to iteratively update the distance matrix $dist$ and the next node matrix $next$, such that $dist[i][j]$ contains the shortest distance from node $i$ to $j$, and $next[i][j]$ contains the next node on the shortest path from $i$ to $j$.
  • Usage: Useful for finding shortest paths between all pairs of nodes in a weighted graph, especially when negative weight cycles are not present.

3. reconstructPathFrom: i to: j usingNextMatrix: nextMatrix

  • Description: Reconstructs the shortest path from node $i$ to $j$ using the next node matrix obtained from the Floyd-Warshall algorithm.
  • Usage: Used in conjunction with the Floyd-Warshall algorithm to obtain the actual path, not just the distance.

4. shortestPathFrom: sourceNode to: targetNode in: aGraph

  • Description: Computes the shortest path from the source node to the target node in the given graph using Breadth-First Search (BFS).
  • Usage: Useful for finding the shortest path between two specific nodes in an unweighted graph.

5. shortestPathLengthFrom: sourceNode to: targetNode in: aGraph

  • Description: Computes the length of the shortest path from the source node to the target node in the given graph.
  • Usage: Provides a quick way to get the length (number of edges) of the shortest path without the need for the full path details.

Conclusion

The ShortestPaths class provides a collection of algorithms to efficiently compute the shortest paths in a graph. By encapsulating complex algorithms like Floyd-Warshall and BFS, it enables easy application in various network analyses and routing problems.

Bridges and Articulation Points

The BridgesAndArticulation class provides algorithms to detect and analyze bridges and articulation points in undirected graphs. Bridges are edges that, when removed, increase the number of connected components in a graph. Articulation points, on the other hand, are nodes that, when removed, increase the number of connected components.

Main Methods:

1. articulationsIn: aGraph

  • Description: Identifies articulation points in a given undirected graph.
  • Formula:
    • A node u is an articulation point if one of the following two conditions is true:
      1. u is the root of DFS tree and has two or more children.
      2. u is not the root of DFS tree and it has a child v such that no vertex in the subtree rooted at v has a back edge to one of the ancestors of u.

2. bridgesIn: aGraph

  • Description: Identifies bridges in a given undirected graph.
  • Formula:
    • An edge (u, v) is a bridge if and only if (u, v) is not part of any cycle in the graph. Specifically, if the earliest visited vertex reachable from subtree rooted with v (including v itself) comes after u in DFS, then (u, v) is a bridge.

Utility Methods:

While these are primary methods used internally, they're crucial for the functioning of the main methods:

  1. articulationUtil: Utility function for finding articulation points using DFS.
  2. bridgeUtil: Utility function for finding bridges using DFS.

Conclusion:

The BridgesAndArticulation class offers precise algorithms to understand critical structures within undirected graphs. By identifying bridges and articulation points, we can gain insights into the robustness and vulnerabilities of a network.

Configuration Model Random Graph Generator

The ConfigurationModel class provides methods to create random graphs using the configuration model. This model takes a degree sequence (a list of degree values for each node) and connects the nodes randomly, preserving the degree distribution.

Methods

1. addDirectedEdgeFrom: node1 to: node2 in: aGraph

  • Description: Adds a directed edge from node1 to node2 in the given graph aGraph.
  • Usage: Internal method used in generating a directed graph.

2. addUndirectedEdgeBetween: node1 and: node2 in: aGraph

  • Description: Adds an undirected edge between node1 and node2 in the given graph aGraph.
  • Usage: Internal method used in generating an undirected graph.

3. generateConfigurationModelWithDegreeSequence: degreeSequence directed: isDirected

  • Description: Generates a random graph using the given degree sequence degreeSequence and a flag isDirected to determine if the graph should be directed or undirected.
  • Formula:
    1. Create an empty graph.
    2. Create a list of "stubs" representing the degree of each node.
    3. Shuffle the stubs to randomize connections.
    4. Connect the stubs to form edges, respecting the degree sequence.
    5. If directed, create directed edges; otherwise, create undirected edges.
  • Usage: Main method to generate a graph using the configuration model. Can be used to create both directed and undirected graphs.

Example

Here's an example of how to create a random undirected graph with a given degree sequence:

| degreeSequence graph |
degreeSequence := #(3 2 2 1).
graph := ConfigurationModel new generateConfigurationModelWithDegreeSequence: degreeSequence directed: false.