hornet.network – Graph Representations & Interactions

Graph Primitives

The basic data structure of hornet.network is the graph (we currently use networkx.DiGraph to implement this graph from NetworkX).

There are two core components to a graph, the Node and the Edge.

Node

A node represents a person or thing in the network. HORNET stores nodes as hornet.network.Node objects. This object contains an identifier of the node as well as important information about the node. Two nodes are considered equal if their ids are equal:

Node('Joe')
class hornet.network.Node(id, size=0)

Class that represents a node in a graph.

>>> Node('abc')
<Node('abc', size=0)>

Edge

An edge is a way of connecting two nodes. Edges are represented by tuples with a length of 3. The first two elements in the tuple are the nodes that form the edge. The third element is hornet.network.EdgeDetail which contains information about the edge:

(Node('Joe'), Node('Jane'), EdgeDetail())

support_{X\Rightarrow Y}=\frac{|e_{X,Y}|}{\overset{E}{\sum}|e|}

confidence_{X\Rightarrow Y}=\frac{support_{X\Rightarrow Y}}{|X|}

Edges can be either directed or undirected. If the graph is undirected,

class hornet.network.EdgeDetail(**kw)

Structure that holds details about an edge, such as the similarity and the size. EdgeDetail objects are not hashable, thus not suitable to be used as keys.

Attributes:

  • similarity
  • size The number of items in common between the two nodes.
  • joint The joint probability of node A and node B, P(A,B) or P(A and B). Also known as the support of a rule.
  • conditional The conditional probability of node B give node A, P(B|A). Also known as the confidence of a rule.

These attributes default to 0. They can optionally be set as keyed arguments to the constructor:

>>> d = EdgeDetail(size=450, joint=0.3, conditional=0.7)
items()
Returns a list of tuples for the attributes of the EdgeDetail.

Basic Graph Interactions

HORNET provides a set of basic primitives for creating and manipulating a graph.

hornet.network.create_directed_graph(**kw)
Create a new directed graph object. The optional kw will become attributes on the graph’s meta object.
hornet.network.create_empty_copy(graph)
Creates a completely empty copy of graph. Useful for making sure that you create the same type of graph (directed vs. undirected).
hornet.network.copy_graph(graph)
Returns a deep copy of the graph.
hornet.network.create_edge(node1, node2, **kw)

Creates a new edge in the form node1 -> node2. The function is the same for both directed and undirected edges.

Additional arguments are set as attributes to the edge.

hornet.network.add_edge(graph, node1, node2, **kw)

Creates a new edge of the form node1 -> node2, adding a reference to it into graph and always nodeA. If the graph is undirected, nodeB also gets a reference to the edge. The values for this edge’s EdgeDetails can be specified as kw.

Returns the newly created edge.

hornet.network.remove_edge(graph, edge)
Safely removes all references to the edge in the graph.
>>> # create a graph
>>> g = create_directed_graph()

>>> # add an edge to the graph
>>> e = add_edge(g, Node('x'), Node('y'), size=15)
>>> g.edges(data=True)
[(<Node('x', size=0)>, <Node('y', size=0)>, <EdgeDetail(size=15)>)]

>>> # copy the graph
>>> h = copy_graph(g)
>>> id(h) != id(g) # they are different objects
True

>>> # remove the edge from the graph
>>> remove_edge(g, e)
>>> g.edges()
[]

>>> # if we just want an edge without adding it to a graph
>>> create_edge('x', 'y', size=4)
('x', 'y', <EdgeDetail(size=4)>)

Filtering

Filtering is the process of removing edges from a graph. The prune performs the filtering. It requires a filtering function. Which is applied to each edge in the graph. If the filtering function determines that an edge should be kept, it will return True, and prune will not remove the edge.

Filtering Functions

Edge Sorting Functions

Sorting a set of edges is useful for determining which edges have the highest conditional or joint probabilities, or the highest similarities. Sorting is also useful when creating a random version of the graph.

hornet.network.sort_no_op(tosort)
Sort function that simply returns the exact list to sort.
hornet.network.sort_random(tosort)
Performs a random shuffle of the tosort list. This function modifies tosort.
hornet.network.sort_similarity(tosort)
Sort a list of edges according to the similarity of the two nodes. Assumes the edge has a similarity properties set.
hornet.network.sort_edge_details(tosort, attribute)
Sort a list of edges according to the attribute of EdgeDetail in each edge.

Randomization

Builder Helpers

hornet.network.rule_generation(graph, denominator_fn=<function attribute_count at 0x1ba58c0>)

Generates association rules for the graph. Assumes a directed graph, and is ‘destructive’ in that it assigns a confidence and a support to each edge in the graph.

  • denominator_fn is the function on which to normalize the edge sizes by. By default, hornet.network.attribute_count() is used, but hornet.network.transaction_count() is also valid.
hornet.network.transaction_count(graph)
Count the number of transactions that occur within the graph. The transactions are found in the ‘size’ element. If graph is directed and there two edges that are bidirectional, the sizes of both edges will be added.

Measurements

hornet.network.transaction_count(graph)
Count the number of transactions that occur within the graph. The transactions are found in the ‘size’ element. If graph is directed and there two edges that are bidirectional, the sizes of both edges will be added.

reciprocity=\dfrac{\overset{E}{\sum}reciprocal_{e}}{\overset{N}{\sum}|E_{n}|}

reciprocal_{e}=\begin{cases}
1 & if\: e_{n,x}\in E_{n}\: and\: e_{x,n}\in E_{x}\\
0 & otherwise\end{cases}

satisfaction=\dfrac{\overset{N}{\sum}satisfied_{n}}{|N|}

satisfied_{n}=\begin{cases}
1, & if\:\exists e\in E_{n}\: s.t.\: reciprocal_{e}=1\\
0, & otherwise\end{cases}

hornet.network.edge_occurrences(graphs)
Counts the occurrences of each edge across a list of graphs.