Search

Contagion processes have been proven to fundamentally depend on the structural properties of the interaction networks conveying them. Many real networked systems are characterized by clustered substructures representing either collections of all-to-all pair-wise interactions (cliques) and/or group interactions, involving many of their members at once. In this work, focusing on interaction structures represented as simplicial complexes, we present a discrete-time microscopic model of complex contagion for a susceptible-infected-susceptible dynamics. Introducing a particular edge clique cover and a heuristic to find it, the model accounts for the higher-order dynamical correlations among the members of the substructures (cliques/simplices). The analytical computation of the critical point reveals that higher-order correlations are responsible for its dependence on the higher-order couplings. While such dependence eludes any mean-field model, the possibility of a bi-stable region is extended to structured populations. Higher-order contagion models capture opinion dynamics and adoption of behavior in social networks. In this paper, the authors propose a mathematical framework able to accurately characterize the phase diagram of these contagion processes in social higher-order networks. [ABSTRACT FROM AUTHOR]

In a wide variety of emerging data-intensive applications, such as social network analysis, Web document clustering, entity resolution, and detection of consistently co-expressed genes in systems biology, the detection of dense subgraphs (cliques) is an essential component. Unfortunately, this problem is NP-Complete and thus computationally intensive at scale-hence there is a need for efficient processing, as well as the techniques for distributing the computation across multiple machines such that the computation, which is too time-consuming on a single machine, can be efficiently performed on a machine cluster given that it is large enough. In this paper, we propose a new algorithm (called GP) for maximal clique enumeration. It identifies cliques by the operation of binary graph partitioning, which iteratively divides a graph until each task is sufficiently small to be processed in parallel. Given a connected graph $$G=(V,E)$$ , the GP algorithm has a space complexity of O(| E|) and a time complexity of $$O(|E|\mu (G))$$ , where $$\mu (G)$$ represents the number of different cliques existing in G. We also present a hybrid algorithm, which can effectively leverage the advantages of both the GP algorithm and the classical Bron-and-Kerbosch (BK) algorithm. Then, we develop corresponding parallel solutions based on the GP and hybrid algorithms. Finally, we evaluate the performance of the proposed solutions on real and synthetic graph data. Our extensive experiments show that in both centralized and parallel setting, our proposed GP and hybrid approaches achieve considerably better performance than the state-of-the-art BK approach. Our parallel solutions are implemented and evaluated on MapReduce, a popular shared-nothing parallel framework, but can easily generalize to other shared-nothing or shared-memory parallel frameworks. [ABSTRACT FROM AUTHOR]

Detecting quasi-cliques in graphs is a useful tool for detecting dense clusters in graph-based data mining. Particularly in large-scale data sets that are error-prone, cliques are overly restrictive and impractical. Quasi-clique detection has been accomplished using heuristic approaches in various applications of graph-based data mining in protein interaction networks, gene co-expression networks, and telecommunication networks. Quasi-cliques are not hereditary, in the sense that every subset of a quasi-clique need not be a quasi-clique. This lack of heredity introduces interesting challenges in the development of exact algorithms to detect maximum cardinality quasi-cliques. The only exact approaches for this problem are limited to two mixed integer programming formulations that were recently proposed in the literature. The main contribution of this article is a new combinatorial branch-and-bound algorithm for the maximum quasi-clique problem. [ABSTRACT FROM AUTHOR]

Cyber-bullying, and other issues related to violence being committed online in prosocial environments, are beginning to constitute an emergency worldwide. Institutions are particularly sensitive to the problem especially as far as teenagers are concerned inasmuch as, in cases of inter-teen episodes, the deterrent power of ordinary justice (i.e. threaten to sue) is not as effective as it is between adults. In order to develop the most suitable policies, institution should not be satisfied with statistics and sociological perspectives on the phenomenon, but rather seek a deep ethical understanding—also referring to the biological and evolutionary past of human beings. The aim of this paper is to show a way to fill this theoretical gap, offering some answers (and some questions too) that can illuminate future policy-oriented research and reflection. In order to do so, we will start by connecting our argument to evolutionary studies carried out in the past two decades, focusing on gossip as a tool for social assortment, thus endowed with a dual function: protect the group from free riders, intruders and bullies but also bully the deviant members. In the “Mediating gossip through social networks” section, we will see which aspects of gossip, vital for bullying, are co-opted by social network scenarios. A fundamental trait of human social life, that is the subdivision in smaller coalitions, or sub-groups, will be shown as missing in social networks (SN) dynamics—therefore constituting themselves as structurally violent. The “Why and how do social networks empower bullying?” section will deal with techno-ethical and epistemological concerns regarding how gossip, mediated by SN, manages to empower cyber-bullying. The “Self-gossip and self-mobbing in the light of the disruption of sub-moralities” section will characterize cyber-bullying as often sparked by self-gossip (soon degrading into self-mobbing) in a scenario where familiar sub-groups, which also mediate defense and mutual understanding, are disrupted. The “Discussion and conclusion” section will consist of a philosophical summary, divided in two parts: a pars destruens analyzing whether SN, in their actual configurations, are fit for being used by humans-like-us, and a pars construens examining the broad potential consequences of highly enforced regulation aimed at contrasting cyber-bullying. [ABSTRACT FROM AUTHOR]

A classical model for social-influence-driven opinion change is the threshold model. Here we study cascades of opinion change driven by threshold model dynamics in the case where multiple initiators trigger the cascade, and where all nodes possess the same adoption threshold ø. Specifically, using empirical and stylized models of social networks, we study cascade size as a function of the initiator fractionp.We find that even for arbitrarily high value of ø, there exists a critical initiator fraction pc(ø) beyond which the cascade becomes global. Network structure, in particular clustering, plays a significant role in this scenario. Similarly to the case of single-node or single-clique initiators studied previously, we observe that community structure within the network facilitates opinion spread to a larger extent than a homogeneous random network. Finally, we study the efficacy of different initiator selection strategies on the size of the cascade and the cascade window. [ABSTRACT FROM AUTHOR]

We model the forming and dynamics of opinions in a social network with Markov chains. We set and solve, for a number of special cases, the problems of controlling agent opinions and game-theoretic problems of informational conflict. [ABSTRACT FROM AUTHOR]

From the perspective of social exchange theory, we explore the downside of social networking. In particular, we discuss the impact of network properties on cronyism. We identify two types of network, clique and entrepreneurial, and two forms of competition, inter- and intra-network. We argue that network competition generally increases the likelihood of cronyism, and the effect of competition on cronyism is moderated by network type. We outline directions for future research and derive practical implications. [ABSTRACT FROM AUTHOR]

Peer relationships are commonly thought to be critical for adolescent socialization, including the development of negative health behaviors such as alcohol and tobacco use. The interplay between genetic liability and peer influences on the development of adolescent alcohol and tobacco use was examined using a nationally-representative sample of adolescent sibling pairs and their best friends. Genetic factors, some of them related to an adolescent’s own substance use and some of them independent of use, were associated with increased exposure to best friends with heavy substance use—a gene-environment correlation. Moreover, adolescents who were genetically liable to substance use were more vulnerable to the adverse influences of their best friends—a gene-environment interaction. [ABSTRACT FROM AUTHOR]

Examines transnational ethnic social networks based on ancestral and kinship ties as a form of social capital that facilitates economic growth in a transborder and regional context. Conceptualization of transnational ethnic social capital; Role of transnational ethnic social capital; Insufficiency of transnational ethnic social capital.

The article presents two essays related to sociology. Individual within an organizational hierarchy possesses informal and formal connections and ties with others in other organizational hierarchies. The informal connections have their origins in extra-institutional relationships based on such considerations as kinship, membership in fraternal or sororal organizations, old school ties based on graduation from the same educational institution or graduating class, common war-time experiences, common ethnic, migrant, community of origin or religious affiliations, or, relationships established at earlier career stages in offices of other organizations and industries which may be re-invoked at later career stages. The specific characteristic of inter-institutional cliques is that their members' loyalties arise outside the framework of organizational and institutional participation. As networks, inter-institutional cliques have no formal definition of membership but rather share a subliminal recognition of like-mindedness based either on personal attraction or recognition of common personal interest. Such networks have no precise definition of the limits of membership, but rather there are star members and peripheral members who have interlocking memberships in other networks surrounding other star members: star members are those who control resources, jobs and other forms of opportunity for clique members.

This paper focuses on one type of linkage among firms, that is, subgroups based on other types of linkage, such as communication, conflict and market relations. Subgroups of organizations within larger interorganizational networks such as distribution channels represent an important focus of attention. Subgroups may represent loci of power and bases of competition in a channel that affect channel functioning. Such subgroups may not be readily identifiable from an examination of individual firm characteristics but stem from the patterns of relations among the firms. Subgroups of firms, also termed as subsystems or cliques in this article, are sets of firms within a channel system that have stronger links with each other than they have with other channel members. Many methods have been developed for identifying subgroups. In this paper two important methods are described and used to examine the pattern of subgroups existing in an actual distribution channel.

Based on data collected in the course of the September and November 1980 waves of the National Election Studies, this contextual analysis of interpersonal relations in social net- works presents two major findings: First, the neighborhood as a geographical unit does not appear to be a perceptually salient environment for political behavior; and second, particular neighbors. individually linked to a voter, appear to constitute a social network that has an independent impact on partisan affect for the political parties and their candidates as well as on stability or change in vote preferences as the electoral season goes forward. Thus, although the neighborhood appears to be of minor importance as a political environment, social relations among particular neighbors result in an interpersonal context that has an impact on political behavior. [ABSTRACT FROM AUTHOR]

Massive graphs are ubiquitous and at the heart of many real-world problems and applications ranging from the World Wide Web to social networks. As a result, techniques for compressing graphs have become increasingly important and remains a challenging and unsolved problem. In this work, we propose a graph compression and encoding framework called GraphZIP based on the observation that real-world graphs often form many cliques of a large size. Using this as a foundation, the proposed technique decomposes a graph into a set of large cliques, which is then used to compress and represent the graph succinctly. In particular, disk-resident and in-memory graph encodings are proposed and shown to be effective with three important benefits. First, it reduces the space needed to store the graph on disk (or other permanent storage device) and in-memory. Second, GraphZIP reduces IO traffic involved in using the graph. Third, it reduces the amount of work involved in running an algorithm on the graph. The experiments demonstrate the scalability, flexibility, and effectiveness of the clique-based compression techniques using a collection of networks from various domains. [ABSTRACT FROM AUTHOR]