Analysing code dependency networks

This FsLab Journal shows how to analyse code dependency networks from a compiled .NET assembly. It is a supplementary material to my blog post on Comparing F# and C# with dependency networks.

Requirements:

• Mono.Cecil - a library for analysis of compiled .NET assemblies
• R - statistical programming language that I used for motif analysis and for some plotting.

You need to have R installed on your machine, especially to run the motif analysis. Full source code used in this FsLab journal is available from my GitHub page.

Required NuGet packages including Cecil will download when you build this project in Visual Studio.

Extracting dependency network

As an example, we will work with FSharp.Data.dll which is already a part of this FsLab Journal Project.

1: 

let projectAssembly = __SOURCE_DIRECTORY__ + @"\packages\FSharp.Data.2.0.8\lib\net40\FSharp.Data.dll"

First step is to extract dependency network from the assembly. Nodes in this network are formed by top-level classes or modules. Links represent dependencies.

For this, we will use some functions defined in dependency-network.fs. Code there uses some of the code from Scott Wlaschin's blog post Cycles and modularity in the wild. The following function reads dependencies from the assembly and saves the extracted network in two JSON files, one containing nodes (modules and classes), second one containing links (dependencies).

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 

references...
#load "type-dependency-graph.fs"
#load "dependency-network.fs"

let outputDir = __SOURCE_DIRECTORY__ + "\\data\\"
let project = "FSharp.Data"

DependencyNetwork.generateNetwork project projectAssembly outputDir

There should now be two files in the data folder: FSharp.Data.all.nodes.json and FSharp.Data.all.links.json.

We can examine size of the network using JSON type provider from FSharp.Data.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 

open FSharp.Data

// JSON type provider - provide samples 
type Nodes = JsonProvider<"../../data/FSharp.Data.all.nodes.json">
type Links = JsonProvider<"../../data/FSharp.Data.all.links.json">

let networkSize project = 
    let jsonNodes = Nodes.Load(outputDir + project + ".all.nodes.json")
    let jsonLinks = Links.Load(outputDir + project + ".all.links.json")
    let nodeCount = jsonNodes.Nodes.Length
    let linkCount = jsonLinks.Links.Length
    nodeCount, linkCount

let nodeCount, linkCount = networkSize project
printfn "Number of nodes: %d, number of links: %d" nodeCount linkCount

Number of nodes: 94, number of links: 173

This gives us basic size of the network. For further analysis, we will work with the adjacency matrix representation. Adjacency matrix is a binary matrix that has value \(1\) in row \(i\) and column \(j\) if there is \(i \rightarrow j\) link in the original network. If there is no link, the matrix has \(0\) in that position.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 

open MathNet.Numerics.LinearAlgebra

let getAdjacencyMatrix project = 
    let jsonNodes = Nodes.Load(outputDir + project + ".all.nodes.json")
    let jsonLinks = Links.Load(outputDir + project + ".all.links.json")
    
    // Create adjacency matrix
    let nodeCount = jsonNodes.Nodes.Length
    seq { for link in jsonLinks.Links -> 
            link.Source, link.Target, 1.0 }
    |> SparseMatrix.ofSeqi nodeCount nodeCount

let adjacencyMatrix = getAdjacencyMatrix project

The resulting adjacency matrix is very sparse:

SparseMatrix 94x94-Double 1.96 % Filled
           0            0            0            0            1 ...            0
           0            0            1            0            0 ...            0
           0            0            0            0            1 ...            0
           0            0            0            0            1 ...            0
           0            0            0            0            0 ...            0
           0            0            0            0            0 ...            0
           0            0            0            0            0 ...            0
         ...          ...          ...          ...          ... ...          ...
           0            0            0            0            1 ...            0

Computing basic network statistics

Using adjacency matrix, we can compute several basic network characteristics. For example, how many nodes do not participate in any dependency? These nodes represent standalone modules within the project. In the adjacency matrix, such nodes have only zeros in their corresponding rows and columns because they are not connected to any other node.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 

let isolatedNodes (adjacencyMatrix: Matrix<float>) = 
    // number of rows (columns)
    let n = adjacencyMatrix.RowCount   
    seq { for node in 0..n-1 ->
            if (adjacencyMatrix.Row(node) |> Seq.sum) = 0.0
                && (adjacencyMatrix.Column(node) |> Seq.sum) = 0.0 
            then 1.0 else 0.0 }
    |> Seq.sum

let isolatedCount = isolatedNodes adjacencyMatrix
printfn "Network has %.0f isolated nodes." isolatedCount

Network has 8 isolated nodes.

File with nodes FSharp.Data.all.nodes.json contains also information on the size of code in each node. Code size is equal to the number of CIL instructions in all functions (methods) within a module (class).

We can extract the total size of the project using JSON type provider.

1: 
2: 
3: 
4: 
5: 
6: 
7: 

let getTotalCodeSize project = 
    let jsonNodes = Nodes.Load(outputDir + project + ".all.nodes.json")
    seq { for node in jsonNodes.Nodes -> node.CodeSize }
    |> Seq.sum

let codeSize = getTotalCodeSize project
printfn "Total code size of the project is %d instructions." codeSize

Total code size of the project is 135001 instructions.

Diameter using R

To compute some more advanced graph statistics, we will turn to R with RProvider. To compute network diameter, we will use the igraph package from R. For this step, you need to have an installation of R on your machine. To be able to use package igraph, you will have to open an R session and run the following command:

install.packages("igraph")

Then you need to restart Visual Studio so that RProvider can detect installed packages.

To be able to use the R function for diameters, we need to transform the adjacency matrix into a format that we can pass into R.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 

open RProvider
open RProvider.``base``
open RProvider.igraph

// transform adjacency matrix into igraph adjacency matrix
let igraphNetwork (adjacencyMatrix: Matrix<float>) =
    Array2D.init adjacencyMatrix.RowCount adjacencyMatrix.ColumnCount
        (fun i j -> adjacencyMatrix.[i,j])
    |> R.as_matrix
    |> R.graph_adjacency

let adjacencyMatrixR = igraphNetwork adjacencyMatrix

// compute diameter of the network
let diameter:float = R.diameter(adjacencyMatrixR).GetValue()
printfn "Diameter of the network is %.0f nodes." diameter    

Diameter of the network is 6 nodes.

Graph motifs

Motifs are small subgraphs with defined structure that occur in graphs. We will again use R package igraph to search for motifs in the project. The R function graph_motifs can efficiently count motifs on 3 or 4 nodes. As an input we only need to supply the R adjacency matrix.

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 

let graphMotifs size =
    if size <> 3 && size <> 4 then 
        failwith "Only motifs of size 3 and 4 are supported."
    let (motifs: float []) = R.graph_motifs(adjacencyMatrixR, size).GetValue()
    Array.zip [| 0..motifs.Length-1 |] motifs

let motifs3 = graphMotifs 3
printfn "%A" motifs3

[|(0, nan); (1, nan); (2, 179.0); (3, nan); (4, 248.0); (5, 7.0); (6, 197.0);
  (7, 95.0); (8, 0.0); (9, 11.0); (10, 0.0); (11, 0.0); (12, 0.0); (13, 7.0);
  (14, 0.0); (15, 0.0)|]

The function R.graph_motifs returns counts of each possible motif on 3 nodes in the network, ordered by their isomorphism class. The F# wrapper function graphMotifs returns an array of tupes where the first element is the isomorphism class of the motif and the second element is the motif count.

Arrangements on 3 nodes that are not connected are not considered as motifs and the function returns nan for those. There are 16 possible subgraphs on 3 nodes but only 13 of them are valid motifs.

What motif is the most common in FSharp.Data?

1: 
2: 
3: 
4: 
5: 
6: 
7: 

let mostCommonMotif motifCounts = 
    motifCounts
    |> Array.filter (fun x -> not (Double.IsNaN(snd x)))
    |> Array.maxBy snd

let isoclass, count = mostCommonMotif motifs3
printfn "The most common motif on 3 nodes is motif number %d which occurs %.0f times." isoclass count

The most common motif on 3 nodes is motif number 4 which occurs 248 times.

The isomprhism class itself does not tell us much about the motif. We can find the corresponding graph by plotting it:

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 

let plotMotif size isoclass =
    let isoGraph = R.graph_isocreate(size=size, number=isoclass)
    namedParams [ 
        "x", box isoGraph;
        "edge.arrow.width", box 1;
        "edge.arrow.size", box 1.5;
        "vertex.size", box 50]
    |> R.plot_igraph

plotMotif 3 isoclass

The most common motif in the project is a simple chain of three nodes. We can plot the whole motif profile of the project to get an overview of frequencies of all motifs.

1: 
2: 
3: 
4: 

open FSharp.Charting

Chart.Bar(motifs3, Title="Motif profile", YTitle="Counts", XTitle="Motif")
|> Chart.WithXAxis(Min=0.0,Max=15.0)

Similarly we can find which motif on 4 nodes is the most common in the project.

1: 
2: 
3: 

let motifs4 = graphMotifs 4
let isoclass4, count4 = mostCommonMotif motifs4
printfn "The most common motif on 4 nodes is motif number %d which occurs %.0f times." isoclass4 count4

The most common motif on 4 nodes is motif number 41 which occurs 591 times.

Again, we plot the motif to find out what graph the isomoprhism class corresponds to.

1: 

plotMotif 4 isoclass4