Chapter 7. Building Communities

With more and more people interacting together and communicating, exchanging information, or simply sharing a common interest in different topics, most data science use cases can be addressed using graph representations. Although very large graphs were, for a long time, only used by the Internet giants, government, and national security agencies, it is becoming more common place to work with large graphs containing millions of vertices. Hence, the main challenge of a data scientist will not necessarily be to detect communities and find influencers on graphs, but rather to do so in a fully distributed and efficient way in order to overcome the constraint of scale. This chapter progresses through building a graph example, at scale, using the persons we identified using NLP extraction described in Chapter 6, Scraping Link-Based External Data.

In this chapter, we will cover the following topics:

• Use Spark to extract content from Elasticsearch, build a Graph of person...

Building a graph of persons

We previously used NLP entity recognition to identify persons from an HTML raw text format. In this chapter, we move to a lower level by trying to infer relations between these entities and detect the possible communities surrounding them.

Contact chaining

Within the context of news articles, we first need to ask ourselves a fundamental question. What defines a relation between two entities? The most elegant answer would probably be to study words using the Stanford NLP libraries described in Chapter 6, Scraping Link-Based External Data. Given the following input sentence, which is taken from http://www.ibtimes.co.uk/david-bowie-yoko-ono-says-starmans-death-has-left-big-empty-space-1545160:

"Yoko Ono said she and late husband John Lennon shared a close relationship with David Bowie"

We could easily extract the syntactic tree, a structure that linguists use to model how sentences are grammatically built and where each element is reported with its type such as a noun...

Using the Accumulo database

We have seen a method to read our personRdd object from Elasticsearch and this forms a simple and neat solution for our storage requirements. However, when writing commercial applications, we must always be mindful of security and, at the time of writing, Elasticsearch security is still in development; so it would be useful at this stage to introduce a storage mechanism with native security. This is an important consideration we are using GDELT data that is, of course, open source by definition. In a commercial environment, it is very common for datasets to be confidential or commercially sensitive in some way, and clients will often request details of how their data will be secured long before they discuss the data science aspect itself. It is the authors experience that many a commercial opportunity is lost due to the inability of solution providers to demonstrate a robust and secure data architecture.

Accumulo (http://accumulo.apache.org) is a NoSQL database...

Community detection algorithm

Community detection has become a popular field of research over the past few decades. Sadly, it did not move as fast as the digital world that a true data scientist lives in, with more and more data collected every second. As a result, most of the proposed solutions are simply not suitable for a big data environment.

Although a lot of algorithms suggest a new scalable way for detecting communities, none of them is actually meaning scalable in a sense of distributed algorithms and parallel computing.

Louvain algorithm

Louvain algorithm is probably the most popular and widely used algorithm for detecting communities on undirected weighted graphs.

Note

For more information about Louvain algorithm, refer to the publication: Fast unfolding of communities in large networks. Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre. 2008

The idea is to start with each vertex being the center of its own community. At each step, we look for community neighbors...

GDELT dataset

In order to validate our implementation, we use the GDELT dataset we analyzed in the previous chapter. We extracted all of the communities and spent some time looking at the person names to see whether or not our community clustering was consistent. The full picture of the communities is reported in Figure 7 and has been realized using the Gephi software, where only the top few thousand connections have been imported:

Figure 7: Community detection on January 12

We first observe that most of the communities we detected are totally aligned with the ones we could eyeball on a force-directed layout, giving a good confidence level about the algorithm accuracy.

The Bowie effect

Any well-defined community has been properly identified, and the less obvious ones are the ones surrounding highly connected vertices such as David Bowie. The name David Bowie being heavily mentioned in GDELT articles alongside so many different persons that, on that day of January 12, 2016, it became too large...

Summary

We have discussed and built a real-world implementation of graph communities leveraging the power of a secure and robust architecture. We have outlined the idea that there is no right or wrong solution in the community detection problem space, as it strongly depends on the use case. In a social network context, for example, where vertices are tightly connected together (an edge represents a true connection between two users), the edge weight does not really matter while the triangle approach probably does. In the telecommunication industry, one could be interested in the communities based on the frequency call of a given user A to a user B, hence turning to a weighted algorithm such as Louvain.

We appreciate that building this community algorithm was far from an easy task, and perhaps stretches the goals of this book, but it involves all of the techniques of graph processing in Spark that makes GraphX a fascinating and extensible tool. We introduced the concepts of message passing...