Usage Matrix As a Graph Problem

The best way to understand the types and elements of a graph is to see things in action using NetworkX ( https://networkx.github.io ). Figure 10-1 shows the major use cases (UCs) of a generic Internet of Things (IoT) platform. Suppose that you want to optimize the system using an analytical framework called Usage Matrix. It provides guidance to pinpoint opportunities for tuning the code base. This technique is applicable in many contexts, including data science products. Table 10-1 depicts the template of a usage matrix. Columns denote individual use cases or functions. Rows represent resources or data nodes. Table 10-2 shows one instance of the usage matrix (the values are made up just to illustrate the technique).

Summing down column j designates the relative volume of accesses against all resources caused by that use case. Summing across row i designates the relative volume of accesses against that resource caused by all use cases. Outliers mark the set of columns/rows that are candidates for optimization; that is, the corresponding use cases and/or resources should be prioritized for performance tuning according to the law of diminishing returns. A particular cell’s value is calculated as a_ij = freq_ijn_ijp_j, where freq_ij denotes the use case j’s frequency regarding resource i (how many times use case j visits this resource per unit of time), n_ij shows the number of accesses per one visit, and p_j is the relative priority of use case j.

We can reformulate our optimization task as a graph problem. Nodes (vertices) are use cases and resources, while links (edges) are weighted according to the impact of use cases on resources. The “impact” relationships are unidirectional (from use cases toward resources). The graph also shows other relationships, too. For example, there are directional edges denoting specific include and extend UML constructs for use cases. Finally, actors are also associated with use cases using the “interact” bidirectional relationships. Overall, a graph where one node may have parallel links is called a multigraph ; our graph is a weighted directed multigraph. A graph where all links are bidirectional and have some default weight is an example of an undirected graph.

Now, it is easy to calculate the equivalents of column/row sums. Namely, the sum of links incident to a resource node denotes its row sum (as similar reasoning holds for the use case nodes). We can ask many interesting questions, too. Does actor 1’s usage of a system have higher impact on resources than actor 2’s? Which actor most intensely utilizes the resources? Which actor interacts with most use cases (directly or indirectly)? All answers can be acquired by simply processing the underlying graph using established graph algorithms.

Table 10-1

Generic Template of a Usage Matrix

	UC 1	UCj	UCn
R 1
R i		a ij
R m

Table 10-2

Sample Instance of Usage Matrix Template

	Row Total	Communicate	Manage Dev.	Exec. Data Analytics	Use Bus. Int.	Use Op. Int.
Network	615	120*1*5=600	5*3*1=15	0	0	0
Messaging	700	120*1*5=600	0	20*2*3=100	0	0
Database	2660	0	0	30*10*3=900	40*10*2=800	80*3*4=960
Column Total		1200	15	1000	800	960

The concrete numbers in Table 10-2 are made up and not important. The Send/Receive use case isn’t included explicitly in Table 10-2 because it is part of other use cases. Of course, you may structure the table differently. At any rate, this UC will be associated with the other UC via the dedicated relationship type. Note that the UML extend mechanism isn’t the same as subclassing in Python and we don’t talk here about inheritance. Based on this table, we see that improving the database (possibly using separate technologies for real-time data acquisition and analytics) is most beneficial.

Caution

I advise you to make a copy of the graph before adding visual effects and relabeling nodes (use the copy parameter to perform the operation in place). If you are not careful with the latter, then you may waste lots of time trying to decipher what is going on with the rest of your code (written to use the previous labels). Keep your original graph tidy, as it should serve as a source of truth.

For basic drawings, you may rely on the built-in matplotlib engine. However, you shouldn’t use it for more complex drawings because, for example, it is quite tedious to control the sizes and shapes of node boxes in matplotlib. Moreover, as you will encounter later, Graphviz allows you to visualize graphs and run algorithms for controlling layouts. Finding out which resource is the most impacted boils down to calculating the degree of resource nodes by using the in_degree method on a graph (keep in mind the directionality of edges). The only caveat is that you must specify the weight argument (in our case, it would point to the custom weight property of associated edges). In an undirected graph, you would simply use the degree method.

Partitioning the Model into a Bipartite Graph

An important category of graphs is bipartite graphs, where nodes can be segregated into two disjunct sets L(eft) and R(ight). Edges are only allowed between nodes from disparate sets; that is, no edge may connect two nodes in set L or R. For example, in a recommender system, a set of users and a set of movies form a bipartite graph for the rated relation . It makes no sense for two users or two movies to rate each other. Therefore, there is only an edge between a user and a movie, if that user has rated that movie. The weight of the edge would be the actual rating.

Let’s add a new edge to our first multigraph G between the Communicate use case and the Application actor (see Listing 10-1):

G.add_edge(0, 10, relation="interact")

G.add_edge(10, 0, relation="interact")

This models the fact that an IoT platform may behave like a virtual device in a federated IoT network. Namely, it can act as an aggregator for a set of subordinate devices and behave as a new device from the perspective of higher-level subsystems. The set of actors and use cases should form a bipartite graph. Listing 10-3 illustrates the procedure to form this type of graph using NetworkX. Here, bipartite.py creates a bipartite graph from our original multigraph by selecting only pertinent nodes and edges. (Note that this code assumes that you have already run usage_matrix.py so that everything is set up.)

from networkx.algorithms import bipartite

# Add two new edges as previously described.

G.add_edge(0, 10, relation="interact")

G.add_edge(10, 0, relation="interact")

# Select all nodes and edges from G that participate in 'interact' relation and

# create an undirected graph from them.

H = nx.Graph()

H.add_edges_from((u, v) for u, v, r in G.edges(data='relation') if r == 'interact')

# Attach a marker to specify which nodes belong to what group.

for node_id in H.nodes():

    H.node[node_id]['bipartite'] = G.node[node_id]['role'] == 'actor'

nx.relabel_nodes(H, {n: G.node[n]['label'].replace(' ', ' ') for n in H.nodes()}, copy=False)

print("Validating that H is bipartite: ", bipartite.is_bipartite(H))

# This is a graph projection operation. Here, we seek to find out what use cases

# have common actors. The weights represent the commonality factor.

W = bipartite.weighted_projected_graph(H, [n for n, r in H.nodes(data='bipartite') if r == 0])

# Draw the graph using matplotlib under the hood.

pos = nx.shell_layout(W)

nx.draw(W, pos=pos, with_labels=True, node_size=800, font_size=12)

nx.draw_networkx_edge_labels(W, pos=pos,

                             edge_labels={(u, v): d['weight']

                                          for u, v, d in W.edges(data=True)})

Listing 10-3

Module bipartite.py Creating a Bipartite Graph from Our Original Multigraph

NetworkX doesn’t use a separate graph type for a bipartite graph. Instead, it uses an algorithm that works on usual graph types. Figure 10-3 shows the weighted projected graph.

Social Networks

There are many ways to describe social networks, but we will assume in this section that social network means any network of people where both individual characteristics and relationships are important to understand the real world’s dynamics. In data science, we want to produce actionable insights from data. The story always begins with a compelling question. To reason about reality and answer that question, we need a model. It turns out that representing people as nodes and their relationships as edges in a graph is a viable model. There are lots of metrics to evaluate various properties (both local and global) of a graph. From these we can infer necessary rules and synthesize knowledge. Moreover, measures of a graph may be used as features in machine learning systems (for example, to predict new link creations based on known facts from a training dataset).

The following is the text output produced by this program, and Figure 10-4 shows the resulting graph:

        lcc  eccent  deg-cent  clos-cent  btwn-cent

0  1.000000       3  0.333333       0.50   0.000000

1  1.000000       3  0.333333       0.50   0.000000

2  0.333333       2  0.666667       0.75   0.533333

3  0.500000       2  0.666667       0.75   0.233333

4  0.500000       2  0.666667       0.75   0.233333

5  1.000000       3  0.333333       0.50   0.000000

6  1.000000       3  0.333333       0.50   0.000000

Average clustering coefficient: 0.761904761904762

Transitivity: 0.5454545454545454

Radius: 2

Diameter: 3

Peripherial nodes: [0, 1, 5, 6]

Central nodes: [2, 3, 4]

For example, nodes 2, 3, and 4 all have the same closeness centrality. Nonetheless, the betweenness centrality gives precedence to node 2, as it is on more shortest paths in the network. By judiciously selecting and combining different metrics, you may come up with good indicators of a network.

The local clustering coefficient (LCC) of a node represents the fraction of pairs of the node’s neighbors who are connected. Node 2 has an LCC of is the degree of node 2. LCC embodies people’s tendency to form clusters; in other words, if two persons share a connection, then they tend to become connected, too (a.k.a. triadic closure).

Nodes 2, 3, and 4 are considered central because the maximum shortest path (in our case, measured as the number of hops in a path) to any other node is equal to the radius of the network. The radius of a graph is the minimum eccentricity for all nodes. The eccentricity of a node is the largest distance between this node and all other nodes. The diameter of a graph is the maximum distance between any pair of nodes. Peripheral nodes have eccentricity equal to the diameter. Note that these measures are very susceptible to outliers, in the same way as is the average. By adding a chain of nodes to a network’s periphery, we can easily move the central nodes toward those items. This is why social network are better described with different centrality measures.

The average clustering coefficient is simply a mean of individual clustering coefficients of nodes. The transitivity is another global clustering flag, which is calculated as the ratio of triangles and open triads in a network. For example, the set of nodes 2, 5, and 4 forms an open triad (there is a missing link between nodes 5 and 4 for a triangle). Transitivity puts more weight on high-degree nodes, which is why it is lower than the average clustering coefficient (nodes 2, 3, and 4 as central are heavier penalized for not forming triangles).

The centrality measures try to indicate the importance of nodes in a network. Degree centrality measures the number of connections a node has to other nodes; influential nodes are heavily connected. The closeness centrality says that important nodes are close to other nodes. The betweenness centrality defines a node’s importance by the ratio of shortest paths in a network including the node. There is a similar notion of betweenness centrality for an edge.

Listing 10-8 introduces kind of a “hello world” for social networks, which is the karate club network (it is so famous that NetworkX already includes it as part of the standard library), as shown in Figure 10-5.

import operator

import pandas as pd

import networkx as nx

import matplotlib.pyplot as plt

G = nx.karate_club_graph()

node_colors = ['orange' if props['club'] == 'Officer' else 'blue'

               for _, props in G.nodes(data=True)]

node_sizes = [180 * G.degree(u) for u in G]

plt.figure(figsize=(10, 10))

pos = nx.kamada_kawai_layout(G)

nx.draw_networkx(G, pos,

                 node_size=node_sizes,

                 node_color=node_colors, alpha=0.8,

                 with_labels=False,

                 edge_color='.6')

main_conns = nx.edge_betweenness_centrality(G, normalized=True)

main_conns = sorted(main_conns.items(), key=operator.itemgetter(1), reverse=True)[:5]

main_conns = tuple(map(operator.itemgetter(0), main_conns))

nx.draw_networkx_edges(G, pos, edgelist=main_conns, edge_color="green", alpha=0.5, width=6)

nx.draw_networkx_labels(G, pos,

                        labels={0: G.node[0]['club'], 33: G.node[33]['club']},

                        font_size=15, font_color="white")

candidate_edges = ((8, 15), (30, 21), (29, 28), (1, 6))

nx.draw_networkx_edges(G, pos, edgelist=candidate_edges,

                       edge_color='blue', alpha=0.5, width=2, style="dashed")

nx.draw_networkx_labels(G, pos,

                        labels={u: u for t in candidate_edges for u in t},

                        font_size=13, font_weight="bold", font_color="yellow")

plt.axis('off')

plt.tight_layout();

plt.show()

# Create a data frame to store various centrality measures.

df = pd.DataFrame(index=candidate_edges)

# Add generic and community aware edge features for potential machine learning classification.

df['pref-att'] = list(map(operator.itemgetter(2),

                          nx.preferential_attachment(G, candidate_edges)))

df['jaccard-c'] = list(map(operator.itemgetter(2),

                          nx.jaccard_coefficient(G, candidate_edges)))

df['aa-idx'] = list(map(operator.itemgetter(2),

                          nx.adamic_adar_index(G, candidate_edges)))

df['ccn'] = list(map(operator.itemgetter(2),

                          nx.cn_soundarajan_hopcroft(G, candidate_edges, 'club')))

df['cra'] = list(map(operator.itemgetter(2),

                          nx.ra_index_soundarajan_hopcroft(G, candidate_edges, 'club')))

print(df)

Listing 10-8

karate-network.py Module Exemplifying the Well-Known Karate Club Network (see Exercise 10-3)

There are three more real social networks available in NetworkX (as of the time of writing). You may want to experiment with them as we did here. The visualization part can be easily reused.

When you study a social network, it is an interesting option to generate realistic network models. These networks aim to mimic pertinent properties of real-world networks under consideration. There are many network generators available inside NetworkX, including the popular preferential model (which obeys the power law) and the small-world network (which has a relatively high clustering coefficient and short average path length). The latter tries to mimic the six degrees of separation idea. Once you have a model, then you can compare it with observations (samples) from the real world. If the estimated parameters of a model (like the exponent α and constant C in a preferential model) work well to produce networks close to those from the real world, then real-world phenomena may be analyzed by using graph theory and computation. For example, you can train a classifier using network features (like our metrics) to predict probabilities about future connections.

Summary

Real-world networks are humungous, so they require more scalable approaches than what has been presented here. One plausible choice is to utilize the Stanford Network Analysis Project (SNAP) framework (visit http://snap.stanford.edu ), which has a Python API, too. Storing huge graphs is also an issue. There are specialized database systems for storing graphs and many more graph formats (most of them are documented and supported by NetworkX). One possible selection for a graph database is Neo4j (see https://neo4j.com/developer/python ).

Graphs are used to judge the robustness of real-world networks (such as the Web, transportation infrastructures, electrical power grids, etc.). Robustness is a quality attribute that indicates how well a network is capable of retaining its core structural properties under failures or attacks (when nodes and/or edges disappear). The basic structural property is connectivity. NetworkX has functions for this purpose (for evaluating both nodes and edges): nx.node_connectivity, nx.minimum_node_cut, nx.edge_connectivity, nx.minimum_edge_cut, and nx.all_simple_paths. The functions are applicable for both undirected and directed graphs. Graphs are also the basis for all sorts of search problems in artificial intelligence.

References