"Aggregating Nodes in Social Networks: Finding Cliques in two St. Lawrence University  Social Networks" Faculty Advisor: Dr. Brian C. Ladd, Mathematics, Computer Science and Statistics Dept.

    This study examined the structure of subgroups within the social network of the St. Lawrence University senior class of 2002 as well as the members of the science faculty and staff. Data was collected last year by Aleksandra Portnova, which depicted the social relationships between seniors. She carried out a survey where she asked 385 seniors to indicate other seniors whom they knew and had spoken to during the Spring 2002 semester. She collected data from 271 students, which was stored as an adjacency matrix. Aleks was interested in including as many members of the senior class as possible so she considered any mention of one student by another as a mutual acquaintance; in an effort to clean the data and make the data set size more manageable, I reinterpreted the raw data so that a mutual acquaintance required both students to mention each other. The final “two-way" data set was 70.4% of the original. Cliques in this graph were then found using the Bron and Kerbosch algorithm, which reported 30,215 cliques, many of which were overlapping. This algorithm was originally implemented in Algol 60; I wrote a similar algorithm in C++ programming language and will compare the results of running both algorithms. These results show that although the senior class of 2002 was very well connected (according to Aleksandra’s study), the number of cliques was less than expected – probably because of the conversion to two-way data. A similar study was performed on the science faculty and staff data set.