Social Graphs

The next chapter (Chapter 10) in Algorithms for Dummies is actually very short because it does not go into much mechanical or technical details in parsing social network graphs due to the complexity of working with myriad connections. I would imagine juggling with large datasets and interconnecting relationships just makes things messier and harder to get one’s arm around. I believe the book provides a program that does the actual work of analyzing the social graph; however, the program does not work because I suspect something has changed in the years since the book has been published.

There is also a brief discussion into yet another way of traversing graphs; this time a sort of random walk around the graphs.

It bears repeating that these types of posts on this website are just my notes; they are just my way of processing what I’m reading, so I don’t think these notes will do anyone else much good.

Here are my notes:

Concepts/definitions found in the chapter

“Social Network Analysis (SNA) is the process of studying interactions in social networks using graphs called sociograms, in which nodes (such as Facebook page) appear as points, and ties (such as external page links) appear as lines.” Algorithms for Dummies, John Paul Mueller and Luca Massaron, 2017, P.198.

Clusters or communities: once you identify clusters or communities of relationships, you can ascribe group characteristics or attributes because in general, these groups will act in the same way or have the same beliefs. In general.

Friendship graphs: graphs showing relationships such as families, business or friends.

Triads: special “triangle” relationships (or none) between three people. Social networks use the idea of triads to accelerate connections between people. Apparently, the more connections there are, the better for the social network. LinkedIn used open triads to identify new suggested connections.

Closed: all three people know each other

Open: one person knows two others, but the two others do not know each other

Connected pair: two people know each other but the third person is new (meeting someone new)

Unconnected: Three people form a group but they don’t know each other; think of seminars or conferences.

Fruchterman-Reingold force-directed algorithm: an algorithm that creates graphs that are a lot easier to understand by separating out the nodes and edges like the way electrically charged particles arrange themselves. After trying out the other algorithms for arranging the graphs, this one does seem to portray clusters a lot better than the others.

Finding clusters in social networks(?) – finding cliques within clusters/communities (basically a subgraph of a graph). Cliques = groups with maximum connectivity – everyone knows each other, all connections connect with each other. Generally, finding clusters is easy; finding cliques is much harder.

Clique percolation method: Finding cliques requires many computations in a sort of brute force way – going through all the vertexes to see if they are part of a clique. Next, you can find communities/clusters by merging cliques through the use of specialized algorithms called clique percolation method. Here is where I ran into programming problems: the program won’t work. I’ve done some research but I haven’t figured it out yet. I have been able to find where the programs reside so I’ve been digging in there and running experiments but at present time, the program is not working.

Some more advanced concepts of navigating graphs

Why do we navigate graphs? To find out the contents of the graph, to determine how nodes are connected, to update graphs.

Counting degrees of separation: defines the distance between nodes. There is a program that calculates the shortest path between nodes. Useful for determining cost in gas versus cost in time (for example). There is something the authors brought up in this chapter: using directed graphs can be very useful, but they didn’t go into the reason why.

Walking graphs randomly: sometimes you want to do random walk to simulate natural activities such as animals foraging for food, might use it for playing games, or might need to pick a random route because normal short route has a traffic jam.

The next chapter

The next chapter looks like a discussion on searching the web for web pages so I'm thinking that this chapter will also lead to some cursory notes because searching the web has got to be a very difficult problem that would not be elucidated in a book for dummies. Again, the materials will be more of an introductory nature much like this chapter on social graphs.