Considering a clique as a conservative definition of community structure, we examine how graph partitioning algorithms interact with cliques. Many popular community-finding algorithms partition the entire graph into non-overlapping communities. We show that on a wide range of empirical networks, from different domains, significant numbers of cliques are split across the separate partitions produced by these algorithms. We then examine the largest connected component of the subgraph formed by retaining only edges in cliques, and apply partitioning strategies that explicitly minimise the number of cliques split. We further examine several modern overlapping community finding algorithms, in terms of the interaction between cliques and the communities they find, and in terms of the global overlap of the sets of communities they find. We conclude that, due to the connectedness of many networks, any community finding algorithm that produces partitions must fail to find at least some significant structures. Moreover, contrary to traditional intuition, in some empirical networks, strong ties and cliques frequently do cross community boundaries; much community structure is fundamentally overlapping and unpartitionable in nature.
Here, Granovetter is using clique' in the sociological sense, closer to the modern idea of community, and the idea is that bridges -- narrow connecting links -- need to be crossed to carry information between such cliques. This idea is further summed up in the modern review of Fortunato @cite_0 as: However, this work, in keeping with research @cite_30 @cite_28 on a limited number of other networks, finds evidence that structurally weak ties need not be crossed to traverse the network, contrary to the intuition just described. In fact, we show that while the traditional intuition may be appropriate in some cases, the structure of many empirical networks does indeed lead to cliques crossing the bottleneck' formed by inter-community edges.
@cite_0 @cite_28 @cite_30
2141015754 2136852793 1977186326 2033507223
This paper examines the celebrated "Strength of weak ties" theory of Granovetter(1973). We formalize the theory in terms of two hypotheses: one, for any threeplayers with two links present, the probability of a third link being present isincreasing in the strength of the two ties, and two, the removal of a weak tieincreases average distance in the network more than the removal of a strong tie. We test these hypotheses using data on the network of coauthorship amongeconomists. We find support for the hypothesis of transitivity of strong ties, but we reject thehypothesis that weak ties reduce distance more than strong ties do. We then identify two general features of networks which explain these findings:significant inequality in the distribution of connections across individuals andstronger ties among individuals who have more connections. Social networks transmitting covert or sensitive information cannot use all ties for this purpose. Rather, they can only use a subset of ties that are strong enough to be “trusted”. This paper addresses whether it is still possible, under this restriction, for information to be transmitted widely and rapidly in social networks. We use transitivity as evidence of strong ties, requiring one or more shared contacts in order to count an edge as strong. We examine the effect of removing all non-transitive ties in two real social network data sets, imposing varying thresholds in the number of shared contacts. We observe that transitive ties occupy a large portion of the network and that removing all other ties, while causing some individuals to become disconnected, preserves the majority of the giant connected component. Furthermore, the average shortest path, important for the rapid diffusion of information, increases only slightly relative to the original network. We also evaluate the cost of forming transitive ties by modeling a random graph composed entirely of closed triads and comparing its connectivity and average shortest path with the equivalent Erdos–Renyi random graph. Both the empirical study and random model point to a robustness of strong ties with respect to the connectivity and small world property of social networks. Sociologists since Simmel have been interested in social circles as essential features of friendship networks. Although network analysis has been increasingly used to uncover patterns among social relationships, theoretical explanations of these patterns have been inadequate. This paper presents a theory of the social organization of friendship ties. The approach is based upon Homans's concepts of activities, interactions, and sentiments and upon the concept of extra-network foci organizing social activities and interaction. The theory is contrasted with Heider's balance theory. Implications for transitivity, network bridges, and density of personal networks are discussed and presented as propositions. The focus theory is shown to help explain patterns of friendships in the 1965-66 Detroit Area Study. This paper is intended as a step toward the development of integrated theory to explain interrelationships between networks and other aspects of social structure. Implications for data analysis are discussed. Sociologists have long recognized the importance of patterns in networks of relations that connect individuals with each other. Simmel (1955) described modern society as consisting of loosely connected social circles of relationships. Granovetter (1973) has indicated the general significance of these social circles for communication, community organization, and social conflict. Various studies have supported this picture of the essential patterns in social networks, including Moreno's sociometry (1953), Milgram's "small world" experiments (1967), and Kadushin's observations (1966). Unfortunately, the study of social networks has often been carried out without concern for the origins in the larger social context. Most network analysis ends with description and labeling of patterns; and when explanations of patterns are offered, they frequently rely upon inherent tendencies within networks to become consistent, balanced, or transitive. As a consequence of such atheoretical and or self-contained network theoretical approaches, data are collected and data analysis techniques are devised for It has been shown that the communities of complex networks often overlap with each other. However, there is no effective method to quantify the overlapping community structure. In this paper, we propose a metric to address this problem. Instead of assuming that one node can only belong to one community, our metric assumes that a maximal clique only belongs to one community. In this way, the overlaps between communities are allowed. To identify the overlapping community structure, we construct a maximal clique network from the original network, and prove that the optimization of our metric on the original network is equivalent to the optimization of Newman's modularity on the maximal clique network. Thus the overlapping community structure can be identified through partitioning the maximal clique network using any modularity optimization method. The effectiveness of our metric is demonstrated by extensive tests on both artificial networks and real world networks with a known community structure. The application to the word association network also reproduces excellent results.