279 results on '"*CLIQUES (Sociology)"'
Search Results
2. Network clique cover approximation to analyze complex contagions through group interactions.
- Author
-
Burgio, Giulio, Arenas, Alex, Gómez, Sergio, and Matamalas, Joan T.
- Subjects
- *
CLIQUES (Sociology) , *CONTAGION (Social psychology) , *SOCIAL interaction , *SOCIAL networks , *POPULATION - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
3. Cliques in Sport: Perceptions of Intercollegiate Athletes.
- Author
-
Spink, Kevin S.
- Subjects
- *
CLIQUES (Sociology) , *COLLEGE athletes , *COLLEGE sports , *SOCIAL groups , *SPORTS teams -- Psychology , *SOCIAL context , *SPORTS psychology , *PSYCHOLOGY - Abstract
Although cliques are often referenced in sporting circles, they have received little attention in the group dynamics literature. This is surprising given their potential influence on group-related processes that could ultimately influence team functioning (e.g., Carron & Eys, 2012). The present study examined competitive athletes' perceptions of cliques using semistructured interviews with 18 (nine female, nine male) intercollegiate athletes (Mage = 20.9, SD =1.6) from nine sport teams. Athletes described the formation of cliques as an inevitable and variable process that was influenced by a number of antecedents (e.g., age/tenure, proximity, similarity) and ultimately shaped individual and group outcomes such as isolation, performance, and sport adherence. Further, athletes described positive consequences that emerged when existing cliques exhibited more inclusive behaviors and advanced some areas of focus for the management of cliques within sport teams. Results are discussed from both theoretical and practical perspectives. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
4. The Source and Structure of Girl World: Tina Fey's Mean Girls and Rosalind Wiseman's Queen Bees and Wannabes.
- Author
-
Bentley, D. M. R.
- Subjects
- *
CLIQUES (Sociology) - Abstract
The article examines the relationship between Tina Fey's movie "Mean Girls" and Rosalind Wiseman's book "Queen Bees and Wannabes." Topics discussed include observation on the film's characters which includes Candy Heron, played by Lindsay Lohan, and Regina George, played by Rachel McAdams, what Queen Bee personifies in Wiseman's terms, and clique types identified and delineated by Wiseman.
- Published
- 2019
- Full Text
- View/download PDF
5. Social pressure in opinion dynamics.
- Author
-
Ferraioli, Diodato and Ventre, Carmine
- Subjects
- *
SOCIAL pressure , *ONLINE social networks , *ECONOMIC sociology , *MULTIAGENT systems , *CLIQUES (Sociology) , *HAMILTONIAN graph theory - Abstract
Motivated by privacy and security concerns in online social networks, we study the role of social pressure in opinion dynamics. These are dynamics, introduced in economics and sociology literature, that model the formation of opinions in a social network. We enrich some of the most classical opinion dynamics, by introducing the pressure, increasing with time, to reach an agreement. We prove that for clique social networks, the dynamics always converges to consensus if the social pressure is high enough. Moreover, we provide (tight) bounds on the speed of convergence; these bounds are polynomial in the number of nodes in the network provided that the pressure grows sufficiently fast. We finally look beyond cliques: we characterize the graphs for which consensus is guaranteed, and make some considerations on the computational complexity of checking whether a graph satisfies such a condition. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
6. Redes de investigación transdisciplinar tecnocientífico en contextos reticulares.
- Author
-
ESPINOZA, Rafael and MARÍN-GONZÁLEZ, Freddy
- Subjects
- *
KNOWLEDGE transfer , *SCIENTIFIC knowledge , *CLIQUES (Sociology) , *NETWORK hubs , *TECHNOLOGICAL innovations , *ORGANIZATIONAL structure , *SOCIAL networks , *RESEARCH - Abstract
El artículo tiene como propósito construir fundamentos teóricos para explicar las implicaciones que tienen las estructuras en red en la creación de conocimiento transdisciplinar-tecnocientifico. Se explica cómo las redes denominadas hubs y su dinámica inciden en el incremento de la eficiencia investigativa. Los resultados destacan como la conformación de hubs aumenta la capacidad para innovar en la producción de conocimiento. Se concluye que la disponibilidad de conocimiento transdisciplinar tecnocientífico está asociada al perfil de capacidades de los actores, quienes movilizan la transferencia de conocimiento de acuerdo a las dinámicas de los hubs de investigación. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
7. Counting cliques in parallel without a cluster: Engineering a fork/join algorithm for shared-memory platforms.
- Author
-
Coppa, Emilio, Finocchi, Irene, and Garcia, Renan Leon
- Subjects
- *
PARALLEL algorithms , *WEBGL (Computer program language) , *SUBGRAPHS , *CLIQUES (Sociology) , *SOCIAL networks - Abstract
In this paper we develop simple and fast multicore parallel algorithms for counting the number of k -cliques in large undirected graphs, for any small constant k ≥ 4. Clique counting is an important problem in a variety of network analytics applications. Differently from existing solutions, which mainly target distributed memory settings (e.g., MapReduce), our algorithms work on off-the-shelf shared-memory multicore platforms. We assess the effectiveness of our approach through an extensive experimental analysis on a variety of real-world graphs, considering different clique sizes and scalability on different numbers of cores. The experimental results show that our parallel algorithms largely outperform the running times of highly optimized sequential solutions and gracefully scale to non-trivial values of k even on medium/large graphs. For instance, computing hundreds of billions of cliques for rather demanding Web graphs and social networks requires about 15 min on a 32-core machine. As a by-product of our experimental analysis, we also compute the exact number of k -cliques with at most 20 nodes in many real-world networks from the SNAP repository. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
8. RCPred: RNA complex prediction as a constrained maximum weight clique problem.
- Author
-
Legendre, Audrey, Angel, Eric, and Tahi, Fariza
- Subjects
- *
CLIQUES (Sociology) , *SMALL groups , *SOCIAL classes , *SOCIAL networks , *HEURISTIC , *METHODOLOGY - Abstract
Background: RNAs can interact and form complexes, which have various biological roles. The secondary structure prediction of those complexes is a first step towards the identification of their 3D structure. We propose an original approach that takes advantage of the high number of RNA secondary structure and RNA-RNA interaction prediction tools. We formulate the problem of RNA complex prediction as the determination of the best combination (according to the free energy) of predicted RNA secondary structures and RNA-RNA interactions. Results: We model those predicted structures and interactions as a graph in order to have a combinatorial optimization problem that is a constrained maximum weight clique problem. We propose an heuristic based on Breakout Local Search to solve this problem and a tool, called RCPred, that returns several solutions, including motifs like internal and external pseudoknots. On a large number of complexes, RCPred gives competitive results compared to the methods of the state of the art. Conclusions: We propose in this paper a method called RCPred for the prediction of several secondary structures of RNA complexes, including internal and external pseudoknots. As further works we will propose an improved computation of the global energy and the insertion of 3D motifs in the RNA complexes. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
9. The Moderating Role of Clique Hierarchical Organization on Resource Control by Central Clique Members.
- Author
-
Zarbatany, Lynne, Ellis, Wendy E., Chen, Xinyin, Kinal, Megan, and Boyko, Lisa
- Subjects
- *
CLIQUES (Sociology) , *ADOLESCENT psychology , *CENTRALITY , *PEER relations , *CONTROL (Psychology) , *COMPETITION (Psychology) , *PLAY , *SOCIAL skills , *TEENAGERS' conduct of life , *MEMBERSHIP - Abstract
Accessing resources in peer groups is essential for youth's survival and reproduction. To date, little is known about the behavioral strategies used by socially prominent preadolescent and early adolescent resource controllers in peer cliques, groups of individuals who hang out together during free time at school. Theory suggests that clique hierarchical organization should influence forceful resource control behavior of central (prominent) clique members, but evidence is mixed. This study examined the effects of clique hierarchical organization on forceful behavior used by central clique members to obtain a special toy during a 5-minute resource contest with clique-mates. Participants were 696 children (59.91% girls) ranging from 9 to 14 years (Mage = 11.59) in 147 cliques. Resource control, and prosocial, coercive, and bistrategic (hybrid prosocial and coercive) bids were recorded. Neither centrality nor hierarchy predicted resource control bid use, but centrality and bistrategic bids predicted resource control. Clique stratification (status differences among members) but not clique structure (shape of hierarchy) moderated the outcome of central clique members' bistrategic bids. Bistrategic bids advantaged central members of low-stratified but not highly stratified cliques, indicating that greater power is needed for resource control in cliques with numerous central members. However, high clique stratification did not quell the need for forceful behavior by central (or other) clique members. These findings suggest that for prominent preadolescent and early adolescent clique members, material resource control is the product of both mitigated force and acquiescence by clique-mates. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
10. Detect colluded stock manipulation via clique in trading network.
- Author
-
Shi, Fa-Bin, Sun, Xiao-Qian, Shen, Hua-Wei, and Cheng, Xue-Qi
- Subjects
- *
MARKET manipulation , *CLIQUES (Sociology) , *STOCKS (Finance) , *DATA analysis , *STOCK exchanges - Abstract
Abstract Market manipulation is one of the important issues that draw much attention from academia and industry. Many efforts have been made to detect manipulation in stock market. However, with the development of technology, the means of manipulation become more and more diversified and the effective detection methods remain to be an open problem. Here, we develop a generalized method for colluded traders detection based on transaction data. We investigate the clique of trading network, and find the number and weight of clique are greater in manipulated stocks than that in non-manipulated stocks. We further propose a method to detect colluded traders based on weight of cliques. Results demonstrate that our method is effective at distinguishing the manipulated stocks and the colluded traders. Highlights • We performed an investigation of the clique in stock trading network. • The clique structure in manipulated stock is clear different. • We propose a method to detect the colluded traders based on cliques. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
11. Equilibrium Distributions of Populations of Biological Species on Networks of Social Sites.
- Author
-
Wang, Min, Zhou, Wen, and Wu, Zhijun
- Subjects
- *
ONLINE social networks , *BIOLOGICAL networks , *HABITATS , *CLIQUES (Sociology) , *QUADRATIC programming - Abstract
We investigate the problem of how a population of biological species would distribute over a given network of social sites so that their social contacts through the connected sites can be maximized (or minimized). This problem has applications in modelling the behaviours of social (or solitary) species such as the development of social groups in human society and the spread of solitary animals in distant habitats. We show that this problem can be formulated as an evolutionary game, with the equilibrium state of the game corresponding to a strategy for choosing the residing sites, each with a certain probability, or equivalently, to a distribution of the population on these sites. The game has a symmetric payoff matrix, and can therefore be analyzed via the solution of a corresponding quadratic programme: An equilibrium strategy of the game is a KKT point of the quadratic programme, which may be a local maximizer, local minimizer, or saddle point, but it is evolutionarily stable if and only if it is a strict local maximizer. In general, with a goal to maximize the social contacts, the species tend to spread on network sites where there are dense connections such as a complete subnetwork or in other words, a network clique. We show that at equilibrium, the population may or may not distribute on a network clique, but the stability of the equilibrium state does depend on the structure of the selected subnetwork. In particular, we show that the distribution of the population on a maximal network clique is evolutionarily stable unless the clique is 'attached' to another clique of the same or larger size, when the population may be able to switch or expand to the neighbouring clique to increase or at least maintain its total amount of contacts. However, the distribution of the population on a non-clique subnetwork is always evolutionarily unstable or weakly evolutionarily stable at the very best, for the population can always move away from its current distribution without decreasing its total amount of contacts. We conclude that the strategies to spread on maximal network cliques are not only equilibrium strategies but also evolutionarily more stable than those on non-clique subnetworks, thus theoretically reaffirming the evolutionary advantages of joining social cliques in social networks for social species. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
12. Tabu search with graph reduction for finding maximum balanced bicliques in bipartite graphs.
- Author
-
Zhou, Yi and Hao, Jin-Kao
- Subjects
- *
HEURISTIC algorithms , *CLIQUES (Sociology) , *MATHEMATICAL complex analysis , *BENCHMARKING (Management) , *TABU search algorithm , *BIPARTITE graphs - Abstract
Abstract The Maximum Balanced Biclique Problem is a relevant graph model with a number of applications in diverse domains. However, the problem is NP-hard and thus computationally challenging. In this paper, we introduce a novel metaheuristic algorithm, which combines an effective constraint-based tabu search procedure and two dedicated graph reduction techniques. We verify the effectiveness of the algorithm on 30 classical random benchmark graphs and 25 very large real-life sparse graphs from the popular Koblenz Network Collection (KONECT). The results show that the algorithm improves the best-known results (new lower bounds) for 10 classical benchmarks and obtains the optimal solutions for 14 KONECT instances. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
13. An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication.
- Author
-
Comin, Carlo and Rizzi, Romeo
- Subjects
- *
CLIQUES (Sociology) , *MATRIX multiplications , *POLYNOMIAL time algorithms , *TIME delay systems , *COMPUTATIONAL statistics - Abstract
The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et al. (SIAM J Comput 6(3):505-517, 1977). As any algorithm falling within the Reverse Search paradigm, it performs a DFS visit of a directed tree (the RS-tree) having the objects to be listed (i.e., maximal cliques) as its nodes. In a recursive implementation, the RS-tree corresponds to the recursion tree of the algorithm. The time delay is given by the cost of generating the next child of a node, and Tsukiyama et al. showed it is O(mn). Makino and Uno (in: Hagerup, Katajainen (eds) Algorithm theory: SWAT 2004. Lecture notes in computer science, Springer, Berlin, pp 260-272, 2004) sharpened the time delay to O(nω) by generating all the children of a node in one single shot, which is performed by computing a square fast matrix multiplication. In this paper we further improve the asymptotics for the exploration of the same RS-tree by grouping the offsprings’ computation even further. Our idea is to rely on rectangular fast matrix multiplication in order to compute all children of n2 nodes in one single shot. According to the current upper bounds on square and rectangular fast matrix multiplication, with this the time delay improves from O(n2.3728639) to O(n2.093362), keeping a polynomial work space. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
14. The conjunctive disjunctive graph node kernel for disease gene prioritization.
- Author
-
Tran Van, Dinh, Sperduti, Alessandro, and Costa, Fabrizio
- Subjects
- *
MATHEMATICAL decomposition , *KERNEL (Mathematics) , *CLIQUES (Sociology) , *GENETIC disorders , *MACHINE learning - Abstract
Disease gene prioritization plays an important role in disclosing the relation between genes and diseases and it has attracted much research. As a consequence, a high number of disease gene prioritization methods have been proposed. Among them, graph-based methods are the most promising paradigms due to their ability to naturally represent many types of relations using a graph representation. One key factor of success of graph-based learning methods is the definition of a proper graph node similarity measure normally measured by graph node kernels. However, most approaches share two common limitations: first, they are based on the diffusion phenomenon which does not effectively exploit the nodes’ context; second, they are not able to process the auxiliary information associated to graph nodes. In this paper, we propose an efficient graph node kernel, based on graph decompositions, that not only is able to effectively take into account nodes’ context, but also to exploit additional information available on graph nodes. The key idea is to learn and generalize from small network fragments present in the neighborhood of genes of interest. An empirical evaluation on several biological databases shows that our proposal achieves state-of-the-art results. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
15. DOMINATION PARAMETERS OF A GRAPH AND ITS COMPLEMENT.
- Author
-
DESORMEAUX, WYATT J., HAYNES, TERESA W., and HENNING, MICHAEL A.
- Subjects
- *
GRAPH connectivity , *GRAPH algorithms , *CLIQUES (Sociology) , *GRAPH theory , *BIOMATHEMATICS - Abstract
A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
16. Understanding Processes of Peer Clique Influence in Late Childhood and Early Adolescence.
- Author
-
Ellis, Wendy E. and Zarbatany, Lynne
- Subjects
- *
CHILDREN , *ADOLESCENCE , *CLIQUES (Sociology) , *SOCIAL networks , *INTERPERSONAL relations - Abstract
Cliques, or groups of peers who interact frequently, are a key social context during childhood and adolescence, providing safety and preferential access to resources. Membership in cliques influences behavior and adjustment, but little is known about the processes by which these influences occur. In this article, we identify putative self and clique socialization processes that may account for greater similarity among clique members over time. Greater adherence to clique norms occurs when members are uncertain about their membership or have limited access to valued clique resources, and when cliques control more resources and are more cohesive. We speculate about other clique influence processes, including those that support children's attempts to distinguish themselves from cliquemates. Understanding clique influence processes can inform efforts to help children and youth resist the negative influences of cliques while protecting the benefits of membership. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
17. The structure of matroids with a spanning clique or projective geometry.
- Author
-
Geelen, Jim and Nelson, Peter
- Subjects
- *
INTEGERS , *MATROIDS , *GEOMETRY , *CLIQUES (Sociology) , *COMBINATORICS - Abstract
Let s , n ≥ 2 be integers. We give a qualitative structural description of every matroid M that is spanned by a frame matroid of a complete graph and has no U s , 2 s -minor and no rank- n projective geometry minor, showing that every such matroid is ‘close’ to a frame matroid. We also give a similar description of every matroid M with a spanning projective geometry over a field GF ( q ) as a restriction and with no U s , 2 s -minor and no PG ( n , q ′ ) -minor for any q ′ > q , showing that such an M is ‘close’ to a GF ( q ) -representable matroid. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
18. Fractional clique decompositions of dense graphs and hypergraphs.
- Author
-
Barber, Ben, Kühn, Daniela, Lo, Allan, Montgomery, Richard, and Osthus, Deryk
- Subjects
- *
GRAPHIC methods , *HYPERGRAPHS , *GEOMETRIC vertices , *COMBINATORICS , *CLIQUES (Sociology) - Abstract
Our main result is that every graph G on n ≥ 10 4 r 3 vertices with minimum degree δ ( G ) ≥ ( 1 − 1 / 10 4 r 3 / 2 ) n has a fractional K r -decomposition. Combining this result with recent work of Barber, Kühn, Lo and Osthus leads to the best known minimum degree thresholds for exact (non-fractional) F -decompositions for a wide class of graphs F (including large cliques). For general k -uniform hypergraphs, we give a short argument which shows that there exists a constant c k > 0 such that every k -uniform hypergraph G on n vertices with minimum codegree at least ( 1 − c k / r 2 k − 1 ) n has a fractional K r ( k ) -decomposition, where K r ( k ) is the complete k -uniform hypergraph on r vertices. (Related fractional decomposition results for triangles have been obtained by Dross and for hypergraph cliques by Dukes as well as Yuster.) All the above new results involve purely combinatorial arguments. In particular, this yields a combinatorial proof of Wilson's theorem that every large F -divisible complete graph has an F -decomposition. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
19. Peer Clique Participation of Victimized Children: Characteristics and Implications for Victimization Over a School Year.
- Author
-
Zarbatany, Lynne, Tremblay, Paul F., Ellis, Wendy E., Xinyin Chen, Kinal, Megan, and Boyko, Lisa
- Subjects
- *
FRIENDSHIP , *CRIME victims , *CHILD psychology , *CLIQUES (Sociology) , *SOCIAL conditions of children - Abstract
This study examined aspects of peer clique participation that mitigated victimization by peers over a school year. Participants were 1,033 children age 8-14 years (Mage = 11.81; 444 boys and 589 girls), including 128 (66 boys) victimized children. Cliques (N = 162) and clique participation were assessed by using the Social Cognitive Map, friendship and behavioral nominations, and observed clique interactions. Almost all victimized children (93%) were clique members. On average, their cliques were more mixed-gender, loosely tied, and peripheral in the peer network, and they were more marginal clique members and treated more negatively during clique interactions than were nonvictims. Variation in clique experience revealed that victimization was mitigated over the school year by greater centrality and friendship within cliques and greater clique aggression, and exacerbated by greater clique victimization and age. These findings suggest that allegiance, affection, and power may deter attacks and motivate cliquemates' defense of victims. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
20. Bounding the Clique-Width of H-Free Chordal Graphs.
- Author
-
Brandstädt, Andreas, Dabrowski, Konrad K., Huang, Shenwei, and Paulusma, Daniël
- Subjects
- *
GRAPH theory , *CLIQUES (Sociology) , *CLASSIFICATION , *NUMERICAL analysis , *EQUATIONS - Abstract
A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co-gem are the only two 1-vertex P4-extensions H for which the class of H-free chordal graphs has bounded clique-width. In fact we prove that bull-free chordal and co-chair-free chordal graphs have clique-width at most 3 and 4, respectively. In particular, we find four new classes of H-free chordal graphs of bounded clique-width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H-free chordal graphs has bounded clique-width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
21. Decomposing and Clique-Coloring (Diamond, Odd-Hole)-Free Graphs.
- Author
-
Chudnovsky, Maria and Lo, Irene
- Subjects
- *
GRAPH theory , *CLIQUES (Sociology) , *GEOMETRIC vertices , *MONOCHROMATIC aberration , *GEOMETRIC shapes - Abstract
A diamond is a graph on [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
22. Local Community Detection Based on Small Cliques.
- Author
-
Hamann, Michael, Röhrs, Eike, and Wagner, Dorothea
- Subjects
- *
CLIQUES (Sociology) , *SOCIAL network analysis , *COMMUNITIES , *SMALL groups , *ALGORITHMS - Abstract
Community detection aims to find dense subgraphs in a network. We consider the problem of finding a community locally around a seed node both in unweighted and weighted networks. This is a faster alternative to algorithms that detect communities that cover the whole network when actually only a single community is required. Further, many overlapping community detection algorithms use local community detection algorithms as basic building block. We provide a broad comparison of different existing strategies of expanding a seed node greedily into a community. For this, we conduct an extensive experimental evaluation both on synthetic benchmark graphs as well as real world networks. We show that results both on synthetic as well as real-world networks can be significantly improved by starting from the largest clique in the neighborhood of the seed node. Further, our experiments indicate that algorithms using scores based on triangles outperform other algorithms in most cases. We provide theoretical descriptions as well as open source implementations of all algorithms used. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
23. Structural Holes in Social Networks with Exogenous Cliques.
- Author
-
Rubí-Barceló, Antoni
- Subjects
- *
SOCIAL network analysis , *CLIQUES (Sociology) , *GAME theory , *INTERMEDIATION (Finance) - Abstract
It has been empirically shown that structural holes in social networks enable potential large benefits to those individuals who bridge them (Burt, 2004). The work in Goyal and Vega-Redondo (2007) shows that the large payoff differentials caused by structural holes can persist even when agents strategically add and remove ties to smooth those differentials, thereby providing a game-theoretic rationale for the existence of bridge-agents. The present paper ties back to the initial empirical literature by explicitly assuming that agents are exogenously linked forming cliques, as in a firm environment. In this setting, bridge-agents cannot be sustained under the same conditions of Goyal and Vega-Redondo (2007). Instead, they can be sustained when the deviation possibilities are restricted and only when they connect small groups of agents to the rest. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
24. A population evolution model and its applications to random networks.
- Author
-
Fazekas, I., Noszály, Cs., and Perecsényi, A.
- Subjects
- *
ASYMPTOTIC distribution , *RANDOM graphs , *CLIQUES (Sociology) , *NETWORK theory (Statistical physics) , *SCALE-free network (Statistical physics) - Abstract
Abstract A general population evolution model is considered. Any individual of the population is characterized by its score. Certain general conditions are assumed concerning the number of the individuals and their scores. Asymptotic theorems are obtained for the number of individuals having a fixed score. Then it is proved that the score distribution is scale free. The result is applied to obtain the weight distribution of cliques in a random graph evolution model. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
25. Molecular beacon computing model for maximum weight clique problem.
- Author
-
Yin, Zhixiang, Cui, Jianzhong, and Zhen, Chen
- Subjects
- *
CLIQUES (Sociology) , *OLIGONUCLEOTIDES , *WEIGHT measurement , *ALGORITHMS , *MOLECULAR biology - Abstract
Given an undirected graph with weights on the vertices, the maximum weight clique problem requires finding the clique of the graph which has the maximum weight. The problem is a general form of the maximum clique problem. In this paper, we encode weight of vertex into a unique fixed length oligonucleotide segment and employ sticker model to solve the problem. The proposed method has two distinct characteristics. On one hand, we skip generating initial data pool that contains every possible solution to the problem of interest, the key point of which is constructing the solution instead of searching solution in the vast initial data pool according to logic constraints. On the other hand, oligonucleotide segments are treated like variables which store weights on vertices, no matter what kind of number the weights are, integer or real. Therefore, the proposed method can solve the problem with arbitrary weight values and be applied to solve the other weight-related problem. In addition, molecular beacon is also employed in order to overcome shortcomings of sticker model. Besides, we have analyzed the proposed algorithm’s feasibility. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
26. Exploiting the Formation of Maximal Cliques in Social Networks.
- Author
-
Fei Hao, Doo-Soon Park, and Zheng Pei
- Subjects
- *
SOCIAL networks , *CLIQUES (Sociology) , *LIFE sciences , *PHILOSOPHICAL analysis , *PSEUDOSCIENCE - Abstract
In social networking analysis, there exists a fundamental problem called maximal cliques enumeration(MCE), which has been extensively investigated in many fields, including social networks, biological science, etc. As a matter of fact, the formation principle of maximal cliques that can help us to speed up the detection of maximal cliques from social networks is often ignored by most existing research works. Aiming to exploit the formation of maximal cliques in social networks, this paper pioneers a creative research issue on the detection of bases of maximal cliques in social networks. We propose a formal concept analysis-based approach for detecting the bases of maximal cliques and detection theorem. It is believed that our work can provide a new research solution and direction for future topological structure analysis in various complex networking systems. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
27. Keeping secrets from friends: Exploring the effects of friendship quality, loneliness and self-esteem on secrecy.
- Author
-
Corsano, Paola, Musetti, Alessandro, Caricati, Luca, and Magnani, Barbara
- Subjects
- *
FRIENDSHIP , *CLIQUES (Sociology) , *INTERPERSONAL attraction , *SIGNIFICANT others , *INTIMACY (Psychology) , *LONELINESS , *PRIVACY , *INTERPERSONAL relations , *MEDICAL ethics , *PARENTS , *SELF-perception , *TEENAGERS' conduct of life , *AFFINITY groups , *PSYCHOLOGY - Abstract
The tendency to keep secrets in adolescents has been studied in particular in their relationships with their parents and associated with psychosocial disadvantages. The current study focused on peer relationships and investigated the effects of friendship quality, loneliness in a multidimensional perspective, and self-esteem on secrecy from friends. Italian adolescents (N = 457; 47% male; 100% white) aged between 13 and 19 years (M = 16.11; SD = 1.53) reported their secrecy from friends, peer and parent-related loneliness, aversion and affinity for aloneness, their self-esteem and the quality of their relationships with their friends. The results showed that peer-related loneliness, affinity for aloneness and self-esteem in particular affect keeping secrets from friends, independent of the participant's gender. Moreover, peer-related loneliness and affinity for aloneness mediated the relationship between self-esteem and secrecy. The data were discussed in the light of adolescence developmental tasks. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
28. An enhanced bitstring encoding for exact maximum clique search in sparse graphs.
- Author
-
San Segundo, Pablo, Artieda, Jorge, Batsyn, Mikhail, and Pardalos, Panos M.
- Subjects
- *
CLIQUES (Sociology) , *SPARSE graphs , *ALGORITHMS , *SET theory , *PROBLEM solving - Abstract
This paper describesBBMCW, a new efficient exact maximum clique algorithm tailored for large sparse graphs which can be bit-encoded directly into memory without a heavy performance penalty. These graphs occur in real-life problems when some form of locality may be exploited to reduce their scale. One such example is correspondence graphs derived from data association problems. The new algorithm is based on the bit-parallel kernel used by theBBMCfamily of published exact algorithms.BBMCWemploys a new bitstring encoding that we denote ‘watched’, because it is reminiscent of the ‘watched literal’ technique used in satisfiability and other constraint problems. The new encoding reduces the number of spurious operations computed by theBBMCbit-parallel kernel in large sparse graphs. Moreover,BBMCWalso improves on bound computation proposed in the literature for bit-parallel solvers. Experimental results show that the new algorithm performs better than prior algorithms over data sets of both real and synthetic sparse graphs. In the real data sets, the improvement in performance averages more than two orders of magnitude with respect to the state-of-the-art exact solverIncMaxCLQ. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
29. New analytical lower bounds on the clique number of a graph.
- Author
-
Stozhkov, Vladimir, Pastukhov, Grigory, Boginski, Vladimir, and Pasiliao, Eduardo L.
- Subjects
- *
CLIQUES (Sociology) , *MATHEMATICAL bounds , *RANDOM graphs , *QUADRATIC programming , *PROBLEM solving - Abstract
This paper proposes three new analytical lower bounds on the clique number of a graph and compares these bounds with those previously established in the literature. Two proposed bounds are derived from the well-known Motzkin–Straus quadratic programming formulation for the maximum clique problem. Theoretical results on the comparison of various bounds are established. Computational experiments are performed on random graph models such as the Erdös-Rényi model for uniform graphs and the generalized random graph model for power-law graphs that simulate graphs with different densities and assortativity coefficients. Computational results suggest that the proposed new analytical bounds improve the existing ones on many graph instances. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
30. Enumeration of Maximal Cliques from an Uncertain Graph.
- Author
-
Mukherjee, Arko Provo, Xu, Pan, and Tirthapura, Srikanta
- Subjects
- *
CLIQUES (Sociology) , *DATA mining , *GRAPH theory , *MATHEMATICAL bounds , *ALGORITHMS - Abstract
We consider the enumeration of dense substructures (maximal cliques) from an uncertain graph. For parameter $0 < \alpha < 1$
-maximal cliques possible within a (uncertain) graph. We present an algorithm to enumerate $\alpha$- Published
- 2017
- Full Text
- View/download PDF
31. Insight into the Disciplinary Structure of Nanoscience & Nanotechnology.
- Author
-
Luan, Chunjuan and Porter, Alan L.
- Subjects
- *
NANOSCIENCE , *NANOTECHNOLOGY , *SOCIAL network analysis , *CLUSTER analysis (Statistics) , *CLIQUES (Sociology) - Published
- 2017
- Full Text
- View/download PDF
32. Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete.
- Author
-
Karpiński, Michał
- Subjects
- *
NP-complete problems , *MONOCHROMATIC light , *SATISFIABILITY (Computer science) , *COLORING matter , *CLIQUES (Sociology) - Abstract
In this paper we study a problem of vertex two-coloring of an undirected graph such that there is no monochromatic cycle of the given length. We show that this problem is hard to solve. We give a proof by presenting a reduction from the variation of satisfiability (SAT) problem. We show the nice properties of coloring cliques with two colors which plays pivotal role in the reduction construction. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
33. k-Cliques mining in dynamic social networks based on triadic formal concept analysis.
- Author
-
Hao, Fei, Park, Doo-Soon, Min, Geyong, Jeong, Young-Sik, and Park, Jong-Hyuk
- Subjects
- *
DATA mining , *SOCIAL networks , *CLIQUES (Sociology) , *INTERNET of things , *UBIQUITOUS computing - Abstract
Internet of Things (IoT), an emerging computing paradigm which interconnects various ubiquitous things is facilitating the advancement of computational intelligence. This paper aims at investigating the computation intelligence extraction approach with focus on the dynamic k -clique mining that is an important issue in social network analysis. The k -clique detection problem as one of the fundamental problems in computer science, can assist us to understand the organization style and behavioral patterns of users in social networks. However, real social networks usually evolve over time and it remains a challenge to efficiently detect the k -cliques from dynamic social networks. To address this challenge, this paper proposes an efficient k -clique dynamic detection theorem based on triadic formal concept analysis (TFCA) with completed mathematical proof. With this proposed detection theorem, we prove that the k -cliques detection problem is equivalent to finding the explicit k -cliques generated from k -triadic equiconcepts plus the implicit k -cliques derived from its high-order triadic equiconcepts. Theoretical analysis and experimental results illustrate that the proposed detection algorithm is efficient for finding the k -cliques and exploring the dynamic characteristics of the sub-structures in social networks. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
34. Clique-based Network Coding Technique.
- Author
-
Pandey, Purnendu Shekhar, Purohit, Neetesh, and Verma, Shekhar
- Subjects
- *
CLIQUES (Sociology) , *COMPUTER programming , *WORD recognition , *LINEAR network coding , *DATA packeting - Abstract
The connected dominating set (CDS) approach is used to create a backbone within wireless networks which ultimately result in an increased number of transmissions while also reducing the number of collisions within wireless networks. Network Coding (NC) on the other hand combines the packets which finally end up further reducing the number of transmissions while increasing security within the wireless scenario. The blend of these two approaches has achieved much in terms of coding opportunity, coding gain, robustness towards packet-loss, and increased throughput. But on closer scrutiny, it has been observed that the application of the CDS-based approach along with NC has various problems as well. This approach keeps on combining and sending the packets until all the receivers attain all the packets. Moreover, the CDS--NC-based approach constrains the network, whereas all the NC nodes (dominating nodes) are connected together creating larger numbers of NC nodes, ultimately resulting in a complex network. Our Clique-Based Algorithm, along with the NC approach, not only efficiently deals with the problem concerned with a CDS--NC-based approach but it also deals with the local problem smoothly (local problem are problems confined to problems within the range of a NC node). The comparative results have shown a clear indication that the application of our Clique-Based Algorithm along with the NC approach clearly outperforms the CDS–NC- and the Tree–NC-based approaches in terms of the number of transmissions and the number of coding operations. This technique brings about better throughput, coding opportunity, coding gain, and robustness towards packet loss as compared to CDS–NC- and Tree–NC-based approaches. [ABSTRACT FROM PUBLISHER]
- Published
- 2016
- Full Text
- View/download PDF
35. Electoral control and the human capital of politicians.
- Author
-
Buisseret, Peter and Prato, Carlo
- Subjects
- *
HUMAN capital , *TIME management , *MANAGEMENT of elections , *CLIQUES (Sociology) , *POLITICAL planning , *REPRESENTATIVE government , *CONSTITUENTS (Persons) - Abstract
We develop a model of electoral control in which politicians in a legislative body allocate their time between providing constituency services to their voters, and pursuing the objectives of legislative cliques and factions. While a politician's human capital symmetrically increases his inherent ability to engage in both endeavors, our analysis uncovers an equilibrium bias towards the latter. As a result of the strategic interdependencies among legislators, a trade-off arises between politicians' human capital and voters' ability to exert electoral control. We characterize conditions under which an increase in the human capital of politicians makes voters worse off by encouraging all politicians to divert their attention away from their constituents. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
36. The persistence of cliques in the post-communist state. The case of deniability in drug reimbursement policy in Poland.
- Author
-
Ozierański, Piotr and King, Lawrence
- Subjects
- *
PHARMACEUTICAL policy , *POSTCOMMUNISM , *CLIQUES (Sociology) , *PHARMACEUTICAL industry , *STATE, The - Abstract
This article explores a key question in political sociology: Can post-communist policy-making be described with classical theories of the Western state or do we need a theory of the specificity of the post-communist state? In so doing, we consider Janine Wedel's clique theory, concerned with informal social actors and processes in post-communist transition. We conducted a case study of drug reimbursement policy in Poland, using 109 stakeholder interviews, official documents and media coverage. Drawing on 'sensitizing concepts' from Wedel's theory, especially the notion of 'deniability', we developed an explanation of why Poland's reimbursement policy combined suboptimal outcomes, procedural irregularities with limited accountability of key stakeholders. We argue that deniability was created through four main mechanisms: (1) blurred boundaries between different types of state authority allowing for the dispersion of blame for controversial policy decisions; (2) bridging different sectors by 'institutional nomads', who often escaped existing conflicts of interest regulations; (3) institutional nomads' 'flexible' methods of influence premised on managing roles and representations; and (4) coordination of resources and influence by elite cliques monopolizing exclusive policy expertise. Overall, the greatest power over drug reimbursement was often associated with lowest accountability. We suggest, therefore, that the clique theory can be generalized from its home domain of explanation in foreign aid and privatizations to more technologically advanced policies in Poland and other post-communist countries. This conclusion is not identical, however, with arguing the uniqueness of the post-communist state. Rather, we show potential for using Wedel's account to analyse policy-making in Western democracies and indicate scope for its possible integration with the classical theories of the state. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
37. MSClique: Multiple Structure Discovery through the Maximum Weighted Clique Problem.
- Author
-
Sanroma, Gerard, Penate-Sanchez, Adrian, Alquézar, René, Serratosa, Francesc, Moreno-Noguer, Francesc, Andrade-Cetto, Juan, and González Ballester, Miguel Ángel
- Subjects
- *
CLIQUES (Sociology) , *COMPUTER vision , *AGGLOMERATION (Materials) , *MACHINE-shop practice , *OUTLIERS (Statistics) - Abstract
We present a novel approach for feature correspondence and multiple structure discovery in computer vision. In contrast to existing methods, we exploit the fact that point-sets on the same structure usually lie close to each other, thus forming clusters in the image. Given a pair of input images, we initially extract points of interest and extract hierarchical representations by agglomerative clustering. We use the maximum weighted clique problem to find the set of corresponding clusters with maximum number of inliers representing the multiple structures at the correct scales. Our method is parameter-free and only needs two sets of points along with their tentative correspondences, thus being extremely easy to use. We demonstrate the effectiveness of our method in multiple-structure fitting experiments in both publicly available and in-house datasets. As shown in the experiments, our approach finds a higher number of structures containing fewer outliers compared to state-of-the-art methods. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
38. Bully Victimization: Selection and Influence Within Adolescent Friendship Networks and Cliques.
- Author
-
Lodder, Gerine, Scholte, Ron, Cillessen, Antonius, and Giletta, Matteo
- Subjects
- *
VICTIMS of bullying , *FRIENDSHIP , *CLIQUES (Sociology) , *PEERS , *SCHOOL bullying , *SOCIAL networks - Abstract
Adolescents tend to form friendships with similar peers and, in turn, their friends further influence adolescents' behaviors and attitudes. Emerging work has shown that these selection and influence processes also might extend to bully victimization. However, no prior work has examined selection and influence effects involved in bully victimization within cliques, despite theoretical account emphasizing the importance of cliques in this regard. This study examined selection and influence processes in adolescence regarding bully victimization both at the level of the entire friendship network and the level of cliques. We used a two-wave design (5-month interval). Participants were 543 adolescents (50.1 % male, Mage = 15.8) in secondary education. Stochastic actor-based models indicated that at the level of the larger friendship network, adolescents tended to select friends with similar levels of bully victimization as they themselves. In addition, adolescent friends influenced each other in terms of bully victimization over time. Actor Parter Interdependence models showed that similarities in bully victimization between clique members were not due to selection of clique members. For boys, average clique bully victimization predicted individual bully victimization over time (influence), but not vice versa. No influence was found for girls, indicating that different mechanisms may underlie friend influence on bully victimization for girls and boys. The differences in results at the level of the larger friendship network versus the clique emphasize the importance of taking the type of friendship ties into account in research on selection and influence processes involved in bully victimization. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
39. Structure Matters: The Role of Clique Hierarchy in the Relationship Between Adolescent Social Status and Aggression and Prosociality.
- Author
-
Pattiselanno, Kim, Dijkstra, Jan, Steglich, Christian, Vollebergh, Wilma, and Veenstra, René
- Subjects
- *
CLIQUES (Sociology) , *SOCIAL dominance , *SOCIAL status , *PROSOCIAL behavior , *SOCIAL structure , *PSYCHOLOGY , *AGGRESSION (Psychology) in adolescence , *SOCIAL support - Abstract
Peer cliques form an important context for the social development of adolescents. Although clique members are often similar in social status, also within cliques, status differences exist. How differences in social status between clique members are related to behaviors of its individual members is rather unknown. This study examined to what extent the relationship of individual social status (i.e., perceived popularity) with aggression and prosocial behavior depends on the level of internal clique hierarchy. The sample consists of 2674 adolescents (49.8 % boys), with a mean age of 14.02. We focused specifically on physical and relational aggression, and practical and emotional support, because these behaviors have shown to be of great importance for social relationships and social standing among adolescents. The internal status hierarchy of cliques was based on the variation in individual social status between clique members (i.e., clique hierarchization) and the structure of status scores within a clique (pyramid shape, inverted pyramid, or equal distribution of social status scores) (i.e., clique status structure). The results showed that differences in aggressive and prosocial behaviors were particularly moderated by clique status structure: aggression was stronger related to individual social status in (girls') cliques where the clique status structure reflected an inverted pyramid with relatively more high status adolescents within the clique than low status peers, and prosocial behavior showed a significant relationship with individual social status, again predominantly in inverted pyramid structured (boys' and girls') cliques. Furthermore, these effects differed by types of gender cliques: the associations were found in same gender but not mixed-gender cliques. The findings stress the importance of taking into account internal clique characteristics when studying adolescent social status in relationship to aggression and prosociality. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
40. Clique percolation in random graphs.
- Author
-
Ming Li, Youjin Deng, and Bing-Hong Wang
- Subjects
- *
RANDOM graphs , *PERCOLATION theory , *CLIQUES (Sociology) , *PHASE transitions , *THERMODYNAMICS , *SIMULATION methods & models - Abstract
As a generation of the classical percolation, clique percolation focuses on the connection of cliques in a graph, where the connection of two k cliques means that they share at least l < k vertices. In this paper we develop a theoretical approach to study clique percolation in Erdos-Renyi graphs, which gives not only the exact solutions of the critical point, but also the corresponding order parameter. Based on this, we prove theoretically that the fraction ψ of cliques in the giant clique cluster always makes a continuous phase transition as the classical percolation. However, the fraction ø of vertices in the giant clique cluster for l > 1 makes a step-function-like discontinuous phase transition in the thermodynamic limit and a continuous phase transition for l = 1. More interesting, our analysis shows that at the critical point, the order parameter øc for l > 1 is neither 0 nor 1, but a constant depending on k and l. All these theoretical findings are in agreement with the simulation results, which give theoretical support and clarification for previous simulation studies of clique percolation. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
41. PARALLEL MAXIMUM CLIQUE ALGORITHMS WITH APPLICATIONS TO NETWORK ANALYSIS.
- Author
-
ROSSI, RYAN A., GLEICH, DAVID F., and GEBREMEDHIN, ASSEFAW H.
- Subjects
- *
CLIQUES (Sociology) , *GRAPH theory , *INFORMATION networks , *SUBGRAPHS , *HEURISTIC algorithms - Abstract
We present a fast, parallel maximum clique algorithm for large sparse graphs that is designed to exploit characteristics of social and information networks. The method exhibits a roughly linear runtime scaling over real-world networks ranging from a thousand to a hundred million nodes. In a test on a social network with 1.8 billion edges, the algorithm finds the largest clique in about 20 minutes. At its heart the algorithm employs a branch-and-bound strategy with novel and aggressive pruning techniques. The pruning techniques include the combined use of core numbers of vertices along with a good initial heuristic solution to remove the vast majority of the search space. In addition, the exploration of the search tree is parallelized. During the search, processes immediately communicate changes to upper and lower bounds on the size of the maximum clique. This exchange of information occasionally results in a superlinear speedup because tasks with large search spaces can be pruned by other processes. We demonstrate the impact of the algorithm on applications using two different network analysis problems: computation of temporal strong components in dynamic networks and determination of compression-friendly ordering of nodes of massive networks. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
42. Cliques in the union of graphs.
- Author
-
Aharoni, Ron, Berger, Eli, Chudnovsky, Maria, and Ziani, Juba
- Subjects
- *
GRAPH theory , *CLIQUES (Sociology) , *SET theory , *NUMBER theory , *MATHEMATICAL analysis - Abstract
Let B and R be two simple graphs with vertex set V , and let G ( B , R ) be the simple graph with vertex set V , in which two vertices are adjacent if they are adjacent in at least one of B and R . For X ⊆ V , we denote by B | X the subgraph of B induced by X ; let R | X and G ( B , R ) | X be defined similarly. A clique in a graph is a set of pairwise adjacent vertices. A subset U ⊆ V is obedient if U is the union of a clique of B and a clique of R . Our first result is that if B has no induced cycles of length four, and R has no induced cycles of length four or five, then every clique of G ( B , R ) is obedient. This strengthens a previous result of the second author, stating the same when B has no induced C 4 and R is chordal. The clique number of a graph is the size of its maximum clique. We say that the pair ( B , R ) is additive if for every X ⊆ V , the sum of the clique numbers of B | X and R | X is at least the clique number of G ( B , R ) | X . Our second result is a sufficient condition for additivity of pairs of graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
43. Cliques and colorings in generalized Paley graphs and an approach to synchronization.
- Author
-
Schneider, Csaba and Silva, Ana C.
- Subjects
- *
SYNCHRONIZATION , *CLIQUES (Sociology) , *COLORING matter , *FINITE fields , *DIRECTED graphs , *GEOMETRIC vertices - Abstract
Given a finite field, one can form a directed graph using the field elements as vertices and connecting two vertices if their difference lies in a fixed subgroup of the multiplicative group. If -1 is contained in this fixed subgroup, then we obtain an undirected graph that is referred to as a generalized Paley graph. In this paper, we study generalized Paley graphs whose clique and chromatic numbers coincide and link this theory to the study of the synchronization property in 1-dimensional primitive affine permutation groups. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
44. The Truth About High School.
- Author
-
Adler, Jerry, McCormick, John, Springen, Karen, Pedersen, Daniel, Joseph, Nadine, Figueroa, Ana, and Dickey, Beth
- Subjects
- *
HIGH school students , *CLIQUES (Sociology) , *HIGH school athletes , *SOCIAL groups - Abstract
Reports on the social aspects of high school in the United States. The formation of different cliques; How students are viewed in various groups; Reasons why high school athletes seem to have a dominating power at high schools; Comments.
- Published
- 1999
45. Friends of friends: are indirect connections in social networks important to animal behaviour?
- Author
-
Brent, Lauren J.N.
- Subjects
- *
INTERORGANIZATIONAL networks , *CLIQUES (Sociology) , *CHAIN migration , *ANIMAL behavior , *NETWORK effect - Abstract
Friend of a friend relationships, or the indirect connections between people, influence our health, well-being, financial success and reproductive output. As with humans, social behaviours in other animals often occur within a broad interconnected network of social ties. Yet studies of animal social behaviour tend to focus on associations between pairs of individuals. With the increase in popularity of social network analysis, researchers have started to look beyond the dyad to examine the role of indirect connections in animal societies. Here, I provide an overview of the new knowledge that has been uncovered by these studies. I focus on research that has addressed both the causes of social behaviours, i.e. the cognitive and genetic basis of indirect connections, as well as their consequences, i.e. the impact of indirect connections on social cohesion, information transfer, cultural practices and fitness. From these studies, it is apparent that indirect connections play an important role in animal behaviour, although future research is needed to clarify their contribution. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
46. Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph.
- Author
-
Gimadi, Edward Kh.
- Subjects
- *
PERFORMANCE evaluation , *PROBLEM solving , *APPROXIMATION theory , *EUCLIDEAN geometry , *CLIQUES (Sociology) - Abstract
Some hard-to solve combinatorial problems of finding several disjoint discrete structures in complete weighted graph are considered. Efficient algorithms with performance guarantees are constructed for the Euclidean m -Peripatetic Salesman Problem, m -Weighted Clique Problem and m -Layer Planar three-index Assignment Problem. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
47. The Class of q-Cliqued Graphs: Eigen-Bi-Balanced Characteristic, Designs, and an Entomological Experiment.
- Author
-
Winter, Paul August, Jessop, Carol Lynne, and Zachariades, Costas
- Subjects
- *
GRAPH theory , *EIGENVALUES , *INTEGRALS , *ENTOMOLOGY , *CLIQUES (Sociology) , *GEOMETRIC vertices - Abstract
Much research has involved the consideration of graphs which have subgraphs of a particular kind, such as cliques. Known classes of graphs which are eigen-bi-balanced, that is, they have a pair a, b of nonzero distinct eigenvalues, whose sum and product are integral, have been investigated. In this paper we will define a new class of graphs, called q-cliqued graphs, on q2+1 vertices, which contain q cliques each of order q connected to a central vertex, and then prove that these q-cliqued graphs are eigen-bi-balanced with respect to a conjugate pair whose sum is -1 and product 1-q. These graphs can be regarded as design graphs, and we use a specific example in an entomological experiment. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
48. Uncovering the overlapping community structure of complex networks by maximal cliques.
- Author
-
Li, Junqiu, Wang, Xingyuan, and Cui, Yaozu
- Subjects
- *
NETWORK theory (Statistical physics) , *OVERLAP integral , *MATHEMATICAL programming , *CLIQUES (Sociology) , *DATA analysis , *PERFORMANCE evaluation , *GRAPH theory - Abstract
In this paper, a unique algorithm is proposed to detect overlapping communities in the un-weighted and weighted networks with considerable accuracy. The maximal cliques, overlapping vertex, bridge vertex and isolated vertex are introduced. First, all the maximal cliques are extracted by the algorithm based on the deep and bread searching. Then two maximal cliques can be merged into a larger sub-graph by some given rules. In addition, the proposed algorithm successfully finds overlapping vertices and bridge vertices between communities. Experimental results using some real-world networks data show that the performance of the proposed algorithm is satisfactory. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
49. Thoughts about street gangs as groups, or always know where the nearest exit lies.
- Author
-
Klein, Malcolm W.
- Subjects
- *
GANG members , *MINORITIES , *VIOLENCE , *ASSAULT & battery , *YOUTH gangs , *CLIQUES (Sociology) - Published
- 2014
- Full Text
- View/download PDF
50. The Images of the Clique Operator and Its Square are Different.
- Author
-
De Caria, Pablo
- Subjects
- *
GRAPH theory , *CLIQUES (Sociology) , *OCTAHEDRAL molecules , *SUBGRAPHS , *MATHEMATICS theorems - Abstract
Let [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.