Survey on Social Community Detection <s> Standard Benchmarks, random generated graphs <s> Data from a voluntary association are used to construct a new formal model for a traditional anthropological problem, fission in small groups. The process leading to fission is viewed as an unequal flow of sentiments and information across the ties in a social network. This flow is unequal because it is uniquely constrained by the contextual range and sensitivity of each relationship in the network. The subsequent differential sharing of sentiments leads to the formation of subgroups with more internal stability than the group as a whole, and results in fission. The Ford-Fulkerson labeling algorithm allows an accurate prediction of membership in the subgroups and of the locus of the fission to be made from measurements of the potential for information flow across each edge in the network. Methods for measurement of potential information flow are discussed, and it is shown that all appropriate techniques will generate the same predictions. <s> BIB001 </s> Survey on Social Community Detection <s> Standard Benchmarks, random generated graphs <s> A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known—a collaboration network and a food web—and find that it detects significant and informative community divisions in both cases. <s> BIB002 </s> Survey on Social Community Detection <s> Standard Benchmarks, random generated graphs <s> More than 12 studies of different bottlenose dolphin populations, spanning from tropical to cold temperate waters, have shown that the species typically lives in societies in which relationships among individuals are predominantly fluid. In all cases dolphins lived in small groups characterised by fluid and dynamic interactions and some degree of dispersal from the natal group by both sexes. We describe a small, closed population of bottlenose dolphins living at the southern extreme of the species' range. Individuals live in large, mixed-sex groups in which no permanent emigration/immigration has been observed over the past 7 years. All members within the community are relatively closely associated (average half-weight index>0.4). Both male–male and female–female networks of preferred associates are present, as are long-lasting associations across sexes. The community structure is temporally stable, compared to other bottlenose dolphin populations, and constant companionship seems to be prevalent in the temporal association pattern. Such high degrees of stability are unprecedented in studies of bottlenose dolphins and may be related to the ecological constraints of Doubtful Sound. Fjords are low-productivity systems in which survival may easily require a greater level of co-operation, and hence group stability. These conditions are also present in other cetacean populations forming stable groups. We therefore hypothesise that ecological constraints are important factors shaping social interactions within cetacean societies. <s> BIB003 </s> Survey on Social Community Detection <s> Standard Benchmarks, random generated graphs <s> We propose a procedure for analyzing and characterizing complex networks. We apply this to the social network as constructed from email communications within a medium sized university with about 1700 employees. Email networks provide an accurate and nonintrusive description of the flow of information within human organizations. Our results reveal the self-organization of the network into a state where the distribution of community sizes is self-similar. This suggests that a universal mechanism, responsible for emergence of scaling in other self-organized complex systems, as, for instance, river networks, could also be the underlying driving force in the formation and evolution of social networks. <s> BIB004 </s> Survey on Social Community Detection <s> Standard Benchmarks, random generated graphs <s> A promising approach to graph clustering is based on the intuitive notion of intra-cluster density vs. inter-cluster sparsity. While both formalizations and algorithms focusing on particular aspects of this rather vague concept have been proposed no conclusive argument on their appropriateness has been given. As a first step towards understanding the consequences of particular conceptions, we conducted an experimental evaluation of graph clustering approaches. By combining proven techniques from graph partitioning and geometric clustering, we also introduce a new approach that compares favorably. <s> BIB005
Considered by many researchers as references, several popular real networks are often used as benchmarks. Some of these are cited along with their vertex number v and edge number e: Zachary Karate Club BIB001 (v=34, e=78); a social network of dolphins living in Doubtful Sound (New Zealand) BIB003 (v=62, e=159); college football team games BIB002 (v=115, e=613); University e-mail network BIB004 (v=1133, e=5451); and scientific co-authorship in condensed matter physics  (v=27519, e=116181). For some of these, a final community list for their graphs exists, while for others only the graph structure is present. Girvan-Newman BIB002 designed a random computer-generated graph and community partition scheme with 4 groups and 32 vertices in each group. This set-up has since become a standard benchmark. A new enhanced version of this graph has been designed by Brandes BIB005 . These standard graphs and benchmarks can then be used to compare community results with a particular community detection algorithm by applying the previously defined measures.