Finding entity pairs

Our next step is to create an EntityPairs class that will expect documents that are represented as lists of entities (which is the result of a transform using the EntityExtractor class defined in Chapter 7). We want our class to function as a transformer inside a Scikit-Learn Pipeline, so it must inherit from BaseEstimator and TransformerMixin, as described in Chapter 4. We expect entities inside a single document to be related to each other, so we will add a pairs method, which uses the itertools.permutations function to identify every pair of entities that co-occur in the same document. Our transform method will call the pairs method on each document in the transformed corpus:

import itertools
from sklearn.base import BaseEstimator, TransformerMixin

class EntityPairs(BaseEstimator, TransformerMixin):
    def __init__(self):
        super(EntityPairs, self).__init__()

    def pairs(self, document):
        return list(itertools.permutations(set(document), 2))

    def fit(self, documents, labels=None):
        return self

    def transform(self, documents):
        return [self.pairs(document) for document in documents]

Now we can systematically extract entities from documents and identify pairs. However, we don’t have a convenient way to differentiate pairs of entities that co-occur very frequently from those that appear together only once. We need a way of encoding the strength of the relationships between entities, which we’ll explore in the next section.

Property graphs

The mathematical model of a graph considers only sets of nodes and edges and can be represented as an adjacency matrix, which is useful for a large range of computations. However, it does not provide us with a mechanism for modeling the strength or type of any given relationship. Do the two actors appear in only one document together, or in many? Do they co-occur more frequently in certain genres of articles? In order to support this type of reasoning, we require some way of storing meaningful properties on our nodes and edges.

The property graph model allows us to embed more information into the graph, thereby extending computational ability. In a property graph, nodes are objects with incoming and outgoing edges and usually contain a type field, similar to a table in a relational database. Edges are objects with a source and target, and they typically contain a label field that identifies the type of relationship and a weight field that identifies the strength of the relationship. For graph-based text analytics, we generally use nodes to represent nouns and edges for verbs. Then later, when we move into a modeling phase, this allows us to describe the types of nodes, the labels of links, and the expected structure of the graph.

Implementing the graph extraction

We can now define a class, GraphExtractor, that will not only transform the entities into nodes, but also assign weights to their edges based on the frequency with which those entities co-occur in our corpus. Our class will initialize a NetworkX graph, and then our transform method will iterate through each document (which is a list of entity pairs), checking to see if there is already an edge between them in the graph. If there is, we will increment the edge’s weight property by 1. If the edge does not already exist in the graph, we use the add_edge method to create one with a weight of 1. As with our thesaurus graph construction, the add_edge method will also add a new node to the graph if it encounters a member of a pair that does not already exist in the graph:

import networkx as nx

class GraphExtractor(BaseEstimator,TransformerMixin):
    def __init__(self):
        self.G = nx.Graph()


    def fit(self, documents, labels=None):
        return self

    def transform(self, documents):
        for document in documents:
            for first, second in document:
                if (first, second) in self.G.edges():
                    self.G.edges[(first, second)]['weight'] += 1
                else:
                    self.G.add_edge(first, second, weight=1)
        return self.G

We can now streamline our entity extraction, entity pairing, and graph extraction steps in a Scikit-Learn Pipeline as follows:

if __name__ == '__main__':
    from reader import PickledCorpusReader
    from sklearn.pipeline import Pipeline

    corpus = PickledCorpusReader('../corpus')
    docs = corpus.docs()

    graph = Pipeline([
        ('entities', EntityExtractor()),
        ('pairs', EntityPairs()),
        ('graph', GraphExtractor())
    ])

    G = graph.fit_transform(docs)
    print(nx.info(G))

On a sample of the Baleen corpus, the graph that is constructed has the following statistics:

Name: Entity Graph
Type: Graph
Number of nodes: 29176
Number of edges: 1232644
Average degree:  84.4971

Centrality

In a network context, the most important nodes are central to the graph because they are connected directly or indirectly to the most nodes. Because centrality gives us a means of understanding a particular node’s relationship to its immediate neighbors and extended network, it can help us identify entities with more prestige and influence. In this section we will compare several ways of computing centrality, including degree centrality, betweenness centrality, closeness centrality, eigenvector centrality, and pagerank.

First, we’ll write a function that accepts an arbitrary centrality measure as a keyword argument and uses this measure to rank the top n nodes and assign each node a property with a score. NetworkX implements centrality algorithms as top-level functions that take a graph, G, as its first input and return dictionaries of scores for each node in the graph. This function uses the nx.set_node_attributes() function to map the scores computed by the metric to the nodes:

import heapq
from operator import itemgetter

def nbest_centrality(G, metrics, n=10):
    # Compute the centrality scores for each vertex
    nbest = {}
    for name, metric in metrics.items():
        scores = metric(G)

        # Set the score as a property on each node
        nx.set_node_attributes(G, name=name, values=scores)

        # Find the top n scores and print them along with their index
        topn = heapq.nlargest(n, scores.items(), key=itemgetter(1))
        nbest[name] = topn

    return nbest

We can use this interface to assign scores automatically to each node in order to save them to disk or employ them as visual weights.

The simplest centrality metric, degree centrality, measures popularity by computing the neighborhood size (degree) of each node and then normalizing by the total number of nodes in the graph. Degree centrality is a measure of how connected a node is, which can be a signifier of influence or significance. If degree centrality measures how connected a given node is, betweenness centrality indicates how connected the graph is as a result of that node. Betweenness centrality is computed as the ratio of shortest paths that include a particular node to the total number of shortest paths.

Here we can use our entity extraction pipeline and nbest_centrality function to compare the top 10 most central nodes, with respect to degree and betweenness centrality:

from tabulate import tabulate

corpus = PickledCorpusReader('../corpus')
docs = corpus.docs()

graph = Pipeline([
        ('entities', EntityExtractor()),
        ('pairs', EntityPairs()),
        ('graph', GraphExtractor())
    ])

G = graph.fit_transform(docs)

centralities = {"Degree Centrality" : nx.degree_centrality,
                "Betweenness Centrality" : nx.betweenness_centrality}

centrality = nbest_centrality(G, centralities, 10)

for measure, scores in centrality.items():
    print("Rankings for {}:".format(measure))
    print((tabulate(scores, headers=["Top Terms", "Score"])))
    print("")

In our results, we see that degree and betweenness centrality overlap significantly in their ranks of the most central entities (e.g., “american,” “new york,” “trump,” “twitter”). These are the influential, densely connected nodes whose entities appear in more documents and also sit at major “crossroads” in the graph:

Rankings for Degree Centrality:
Top Terms      Score
----------    ---------
american       0.054093
new york       0.0500643
washington     0.16096
america        0.156744
united states  0.153076
los angeles    0.139537
republican     0.130077
california     0.120617
trump          0.116778
twitter        0.114447

Rankings for Betweenness Centrality:
Top Terms      Score
----------    ---------
american       0.224302
new york       0.214499
america        0.0258287
united states  0.0245601
washington     0.0244075
los angeles    0.0228752
twitter        0.0191998
follow         0.0181923
california     0.0181462
new            0.0180939

While degree and betweenness centrality might be used as a measure of overall celebrity, we frequently find that the most connected node has a large neighborhood, but is disconnected from the majority of nodes in the graph.

Let’s consider the context of a particular egograph, or subgraph, of our full graph that reframes the network from the perspective of one particular node. We can extract this egograph using the NetworkX method nx.ego_graph:

H = nx.ego_graph(G, "hollywood")

Now we have a graph that distills all the relationships to one specific entity (“Hollywood”). Not only does this dramatically reduce the size of our graph (meaning that subsequent searches will be much more efficient), this transformation will also enable us to reason about our entity.

Let’s say we want to identify entities that are closer on average to other entities in the Hollywood graph. Closeness centrality (implemented as nx.closeness_centrality in NetworkX) uses a statistical measure of the outgoing paths for each node and computes the average path distance to all other nodes from a single node, normalized by the size of the graph. The classic interpretation of closeness centrality is that it describes how fast information originating at a specific node will spread throughout the network.

By contrast, eigenvector centrality says that the more important nodes you are connected to, the more important you are, expressing “fame by association.” This means that nodes with a small number of very influential neighbors may outrank nodes with high degrees. Eigenvector centrality is the basis of several variants, including Katz centrality and the famous PageRank algorithm.

We can use our nbest_centrality function to see how each of these centrality measures produces differing determinations of the most important entities in our Hollywood egograph:

hollywood_centralities = {"closeness" : nx.closeness_centrality,
                          "eigenvector" : nx.eigenvector_centrality_numpy,
                          "katz" : nx.katz_centrality_numpy,
                          "pagerank" : nx.pagerank_numpy,}

hollywood_centrality = nbest_centrality(H, hollywood_centralities, 10)
for measure, scores in hollywood_centrality.items():
    print("Rankings for {}:".format(measure))
    print((tabulate(scores, headers=["Top Terms", "Score"])))
    print("")

Our results show that the entities with the highest closeness centrality (e.g., “video,” “british,” “brooklyn”), are not particularly ostentatious, perhaps instead serving as the hidden forces connecting more prominent celebrity structures. Eigenvector, PageRank, and Katz centrality all reduce the impact of degree (e.g., the most commonly occurring entities) and have the effect of showing “the power behind the scenes,” highlights well-connected entities (“republican,” “obama”) and sidekicks:

Rankings for Closeness Centrality:
Top Terms      Score
----------    ---------
hollywood       1
new york        0.687801
los angeles     0.651051
british         0.6356
america         0.629222
american        0.625243
video           0.621315
london          0.612872
china           0.612434
brooklyn        0.607227

Rankings for Eigenvector Centrality:
Top Terms       Score
----------     ---------
hollywood       0.0510389
new york        0.0493439
los angeles     0.0485406
british         0.0480387
video           0.0480122
china           0.0478956
london          0.0477556
twitter         0.0477143
new york city   0.0476534
new             0.0475649

Rankings for PageRank Centrality:
Top Terms       Score
----------     ---------
hollywood       0.0070501
american        0.00581407
new york        0.00561847
trump           0.00521602
republican      0.00513387
america         0.00476237
donald trump    0.00453808
washington      0.00417929
united states   0.00398346
obama           0.00380977

Rankings for Katz Centrality:
Top Terms           Score
----------         ---------
video               0.107601
washington          0.104191
chinese             0.1035
hillary             0.0893112
cleveland           0.087653
state               0.0876141
muslims             0.0840494
editor              0.0818608
paramount pictures  0.0801545
republican party    0.0787887

Structural analysis

As we saw earlier in this chapter, visual analysis of graphs enables us to detect interesting patterns in their structure. We can plot our Hollywood egograph to explore this structure as we did earlier with our thesaurus graph, using the nx.spring_layout method, passing in a k value to specify the minimum distance between nodes, and an iterations keyword argument to ensure the nodes are separate enough to be legible (Figure 9-5).

H = nx.ego_graph(G, "hollywood")
edges, weights = zip(*nx.get_edge_attributes(H, "weight").items())
pos = nx.spring_layout(H, k=0.3, iterations=40)

nx.draw(
    H, pos, node_color="skyblue", node_size=20, edgelist=edges,
    edge_color=weights, width=0.25, edge_cmap=plt.cm.Pastel2,
    with_labels=True, font_size=6, alpha=0.8)
plt.show()

Many larger graphs will suffer from the “hairball effect,” meaning that the nodes and edges are so dense as to make it difficult to effectively discern meaningful structures. In these cases, we often instead try to inspect the degree distribution for all nodes in a network to inform ourselves about its overall structure.

Figure 9-5. Relationships to Hollywood in the Baleen corpus

We can examine this distribution using Seaborn’s distplot method, setting the norm_hist parameter to True so that the height will display degree density rather than raw count:

import seaborn as sns

sns.distplot([G.degree(v) for v in G.nodes()], norm_hist=True)
plt.show()

In most graphs, the majority of nodes have relatively low degree, so we generally expect to observe a high amount of right-skew in their degree distributions, such as in the Baleen Entity Graph plot shown in the upper left of Figure 9-6. The small number of nodes with the highest degrees are hubs due to their frequent occurrence and large number of connections across the corpus.

Interestingly, the degree distributions for certain ego graphs display remarkably different behavior, such as with the Hollywood ego graph exhibiting a nearly symmetric probability distribution, as shown in the upper right of Figure 9-6.

Figure 9-6. Histograms of degree distributions

Other useful structural measures of a network are its clustering coefficient (nx.average_clustering) and transitivity (nx.transitivity), both of which can be used to assess how social a network is. The clustering coefficient is a real number that is 0 when there is no clustering and 1 when the graph consists entirely of disjointed cliques (nx.graph_number_of_cliques). Transitivity tells us the likelihood that two nodes with a common connection are neighbors:

print("Baleen Entity Graph")
print("Average clustering coefficient: {}".format(nx.average_clustering(G)))
print("Transitivity: {}".format(nx.transitivity(G)))
print("Number of cliques: {}".format(nx.graph_number_of_cliques(G)))

print("Hollywood Ego Graph")
print("Average clustering coefficient: {}".format(nx.average_clustering(H)))
print("Transitivity: {}".format(nx.transitivity(H)))
print("Number of cliques: {}".format(nx.graph_number_of_cliques(H)))

Baleen Entity Graph
Average clustering coefficient: 0.7771459590548481
Transitivity: 0.29504798606584176
Number of cliques: 51376

Hollywood Ego Graph
Average clustering coefficient: 0.9214236425410913
Transitivity: 0.6502420989124886
Number of cliques: 348

In the context of our entity graph, the high clustering and transitivity coefficients suggest that our network is extremely social. For instance, in our “Hollywood” ego graph, the transitivity suggests that there is a 65 percent chance that any two entities who share a common connection are themselves neighbors!