Reading Club

Here we began a study of clustering methods applied to graph theory with the goal of understanding community detection in social networks. We began with an application from Oggier, Phetsouvanh and Datta, “BiVA: Bitcoin Network Visualization & Analysis” which applies clustering techniques and entropy centrality to produce visualizations of the transaction network defined by the Bitcoin block chain.

Several members of our reading club had expressed interest in the problem of community finding in social networks. The obvious direction to go was to look at graph clustering algorithms, but first we needed to cover some of the basics of graph analysis. Hence, we began with the classic paper on the PageRank algorithm, “The Anatomy of a Large-Scale HypertextualWeb Search Engine” by Sergey Brin and Lawrence Page.

To give additional background on the subject, we also looked at a more recent expository paper, “Deeper Inside PageRank” by Amy N. Langville and Carl D. Meyer.

We continued studying graphs with social networking applications in mind. We read a paper with obvious importance to social networks, “Opinion maximization in social networks” by Aristides Gionis, Evimaria Terzi and Panayiotis Tsaparas. This paper described a game theoretical method for choosing members of a social network who can spread a change of opinion most efficiently through the network. In other words, the paper describes a mathematical theory for how to find social influencer for a marketing campaign, or public relations campaign.

We continued studying graphs with social networking applications in mind. We read “On efficient use of entropy centrality for social network analysis and community detection” by Alexander G. Nikolaev, Raihan Razib, Ashwin Kucheriya which described a measurement of centrality. Think of a social network as network of merchants trading apples with their neighbors. Consider what happens when one of the apple merchants receives an apple from a trade. There are many possible merchants who were the one that sold that apple first. A merchant is considered central to the network if that merchant is highly likely to be the original merchant given for many other apple merchants as measured by the entropy of the corresponding probability distribution.