Social Network Cohesiveness, Centrality, and Connectedness.

Most networks constantly evolve with time. The rate at which changes in such networks occur can vary considerably. In recent years, the existence of social network sites, such as Facebook and Twitter, has grown exponentially. Social network sites are defined as websites that facilitate the traversal of networks of relationships of mutual acknowledgement. Such sites share similarities with many other types of networks; such as chemical systems, neural networks, the Internet and the World Wide Web. In order to capture the global properties of such networks, one can model them as graphs whose nodes represent the entity, and whose edges stand for the interactions that exist between them.

This dissertation will survey the growth of such networks based on the condition of several structural properties of graphs at different states. A number of efficient algorithms will be implemented to compute the various metrics. The topology of the graphs will be studied for the presence of cliques or large clustering coefficient, and power law degree distribution.

The effects of expansion on a network’s topology and structure based on the theory of preferential attachment will be considered. The generation of random graphs (adding edges chosen uniformly at random) will be modelled separately, and the difference in the properties leading to new construction rather than expansion will be scrutinised.

The intent for this project is to utilise the graph generation methods to construct a large sample dataset, and compute averages of the metrics measured and analyse the distribution of these values as the number of vertices and edges in the graphs vary. Using graph theory and probability theory, an evolution model will be produced that applies to any network that evolves over time, and will depict their structural decompositions.

What happens if a 'person' suddenly leaves a network? What effect will this have on the resulting network? How does information spread through a network if you target the most influential person, and/or groups of people?

Using the generated data, questions like this will be explored and the problem of information diffusion in OSNs will be examined.

The project is being implemented in Java. Some of the metrics computed on the networks will include, clustering coefficients, spectral density, characteristic path length, degree distributions etc. The models implemented will include the model proposed by Barabasi and Albert, and the model proposed by Watts and Strogatz.

Given adequate time following the completion of the objectives in the scope of this project, I will be looking at implementing a web application in Ruby on Rails that invokes the Facebook API and collects insight data on posts made by business accounts. I will use this data to compare real-world examples against the findings of the 'artificial' data.