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
2127048411 2141015754 2136852793
The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i.e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e.g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks. 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.