Search

The number of international schools hit the 6,000-mark in 2012, and the 13,000-mark in 2022. In spite of continuous growth and diversity of provision, paradoxically some literature continues to paint a largely negative sociological imagination, associating the arena with micro-politics, high turnover, and increasing precarity. At the same time, the social reality of working in the arena remains under-reported and under-theorised. The largest number of international schools are now in China, where two-thirds are of the 'non-traditional' type. Our paper focuses on the experiences of two expatriate teachers in that relatively new field. In order to address the questions of 'how do teachers cope?', and 'what strategies do they adopt?', our paper delves into the under-reported social reality of 'cliques'. By adopting a 'positive sociology' lens of inquiry, we begin to address the role that cliques-formation might have in dealing with precarity and insecurity, especially that of 'friendship precarity' caused by constant transitions and short-term contracts. It can be seen that cliques offer a natural, quick, and practical solution to addressing precarity, helping over time to create resilience, and should not be viewed solely within a negative sociological imagination. [ABSTRACT FROM AUTHOR]

A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach nongeometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs. [ABSTRACT FROM AUTHOR]

We propose a multilayer network approach to alliance formation. In a signed affinity layer, agents are partitioned into clusters, with friendly relations within and hostile connections across clusters. Agents then form defensive collaborations in an alliance layer as follows: Agents in the same cluster form a nested split graph with degree inversely correlated to the level of hostility, and agents from disparate clusters with high-degree and low-hostility form cliques. Within cliques, agents from a cluster that is "intermediate" in terms of discord serve as a bridge to interconnect agents from more "extreme" clusters. • The paper examines how alliances are formed in a multi-layer network. • In In the base layer, agents are grouped into clusters in a signed graph. • The alliance network takes the shape of a nested split graph. • In the alliance network, the degree is indirectly linked to the level of hostility. • In the alliance network, the degree is indirectly linked to the level of hostility. • The findings are supported by several real-world examples. [ABSTRACT FROM AUTHOR]

Mantel’s theorem is a classical result in extremal graph theory which implies that the maximum number of edges of a triangle-free graph of order n. In 1970, Nosal obtained a spectral version of Mantel’s theorem which gave the maximum spectral radius of a triangle-free graph of order n. In this paper, the clique tensor of a graph G is proposed and the spectral Mantel’s theorem is extended via the clique tensor. Furthermore, a sharp upper bound of the number of cliques in G via the spectral radius of the clique tensor is obtained. These results imply that a result of Erdős (Magyar Tud Akad Mat Kutató Int Közl 7:459–464, 1962) under certain conditions. [ABSTRACT FROM AUTHOR]

Recently Chase determined the maximum possible number of cliques of size t in a graph on n vertices with given maximum degree. Soon afterward, Chakraborti and Chen answered the version of this question in which we ask that the graph have m edges and fixed maximum degree (without imposing any constraint on the number of vertices). In this paper we address these problems on hypergraphs. For s-graphs with s\geq 3 a number of issues arise that do not appear in the graph case. For instance, for general s-graphs we can assign degrees to any i-subset of the vertex set with 1≤ i ≤ s 1. We establish bounds on the number of t-cliques in an s-graph H with i-degree bounded by Δ in three contexts: H has n vertices; H has m (hyper)edges; and (generalizing the previous case) H has a fixed number p of u-cliques for some u with s≤ u≤ t. When Δ is of a special form we characterize the extremal s-graphs and prove that the bounds are tight. These extremal examples are the shadows of either Steiner systems or partial Steiner systems. On the way to proving our uniqueness results, we extend results of Füredi and Griggs on uniqueness in Kruskal--Katona from the shadow case to the clique case. [ABSTRACT FROM AUTHOR]

Natural language processing is still an emerging field in machine learning. Access to more and more data sets in textual form, new applications for artificial intelligence and the need for simple communication with operating systems all simultaneously affect the importance of natural language processing in evolving artificial intelligence. Traditional methods of textual representation, such as Bag-of-Words, have some limitations that result from the lack of consideration of semantics and dependencies between words. Therefore, we propose a new approach based on graph representations, which takes into account both local context and global relationships between words, allowing for a more expressive textual representation. The aim of the paper is to examine the possibility of using graph representations in natural language processing and to demonstrate their use in text classification. An innovative element of the proposed approach is the use of common cliques in graphs representing documents to create a feature vector. Experiments confirm that the proposed approach can improve classification efficiency. The use of a new text representation method to predict book categories based on the analysis of its content resulted in accuracy, precision, recall and an F1-score of over 90%. Moving from traditional approaches to a graph-based approach could make a big difference in natural language processing and text analysis and could open up new opportunities in the field. [ABSTRACT FROM AUTHOR]

A graph G is q-Ramsey for a q -tuple of graphs (H 1 , ... , H q) if for every q -coloring of the edges of G there exists a monochromatic copy of H i in color i for some i ∈ [ q ]. Over the last few decades, researchers have investigated a number of questions related to this notion, aiming to understand the properties of graphs that are q -Ramsey for a fixed tuple. Among the tools developed while studying questions of this type are gadget graphs, called signal senders and determiners, which have proven invaluable for building Ramsey graphs with certain properties. However, until now these gadgets have been shown to exist and used mainly in the two-color setting or in the symmetric multicolor setting, and our knowledge about their existence for multicolor asymmetric tuples is extremely limited. In this paper, we construct such gadgets for any tuple of cliques. We then use these gadgets to generalize three classical theorems in this area to the asymmetric multicolor setting. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the global clustering coefficient (a.k.a transitivity) and clique number of graphs generated by a preferential attachment random graph model with an additional feature of allowing edge connections between existing vertices. Specifically, at each time step t, either a new vertex is added with probability f(t), or an edge is added between two existing vertices with probability 1 - f (t) . We establish concentration inequalities for the global clustering and clique number of the resulting graphs under the assumption that f(t) is a regularly varying function at infinity with index of regular variation - γ , where γ ∈ [ 0 , 1) . We also demonstrate an inverse relation between these two statistics: the clique number is essentially the reciprocal of the global clustering coefficient. [ABSTRACT FROM AUTHOR]

A graph G is said to be q -Ramsey for a q -tuple of graphs (H1,...,Hq), denoted by G→q(H1,...,Hq), if every q -edge-coloring of G contains a monochromatic copy of Hi in color i for some i∈[q]. Let sq(H1,...,Hq) denote the smallest minimum degree of G over all graphs G that are minimal q -Ramsey for (H1,...,Hq) (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdős, and Lovász, who determined its value precisely for a pair of cliques. Over the past two decades the parameter sq has been studied by several groups of authors, their main focus being on the symmetric case, where Hi≅H for all i∈[q]. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles, and trees. We determine s2(H1,H2) when (H1,H2) is a pair of one clique and one tree, a pair of one clique and one cycle, and a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on sq(Cℓ,...,Cℓ,Kt,...,Kt) in terms of the size of the cliques t, the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed. [ABSTRACT FROM AUTHOR]

In this paper we establish asymptotics (as the size of the graph grows to infinity) for the expected number of cliques in the Chung–Lu inhomogeneous random graph model in which vertices are assigned independent weights which have tail probabilities h 1 - α l (h) , where α > 2 and l is a slowly varying function. Each pair of vertices is connected by an edge with a probability proportional to the product of the weights of those vertices. We present a complete set of asymptotics for all clique sizes and for all non-integer α > 2 . We also explain why the case of an integer α is different, and present partial results for the asymptotics in that case. [ABSTRACT FROM AUTHOR]

Let t be an elements of order 3 in a finite simple group G. Let X = tG be a conjugacy class of t in G. The A4-graph, represented as A4(G, X), is a simple graph has X as a vertex set and two vertices x, y ∈ X, joined by edge whenever x ̸= y and xy−1 = yx−1 . In this paper, we investigate the discs structure and determine the clique number, girth and diameter of A4(G, X) when G is isomorphic to one of the untwisted groups G2(2)′, G2(3) or G2(4). [ABSTRACT FROM AUTHOR]

This paper proposes and investigates a framework for clique gossip protocols. As complete subnetworks, the existence of cliques is ubiquitous in various social, computer, and engineering networks. By clique gossiping, nodes interact with each other along a sequence of cliques. Clique-gossip protocols are defined as arbitrary linear node interactions where node states are vectors evolving as linear dynamical systems. Such protocols become clique-gossip averaging algorithms when node states are scalars under averaging rules. We generalize the classical notion of line graph to capture the essential node interaction structure induced by both the underlying network and the specific clique sequence. We prove a fundamental eigenvalue invariance principle for periodic clique-gossip protocols, which implies that any permutation of the clique sequence leads to the same spectrum for the overall state transition when the generalized line graph contains no cycle. We also prove that for a network with $n$ nodes, cliques with smaller sizes determined by factors of $n$ can always be constructed leading to finite-time convergent clique-gossip averaging algorithms, provided $n$ is not a prime number. Particularly, such finite-time convergence can be achieved with cliques of equal size $m$ if and only if $n$ is divisible by $m$ and they have exactly the same prime factors. A proven fastest finite-time convergent clique-gossip algorithm is constructed for clique-gossiping using size- $m$ cliques. Additionally, the acceleration effects of clique-gossiping are illustrated via numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we propose a network analysis-based approach to help experts in their analyses of subjects with mild cognitive impairment (hereafter, MCI) and Alzheimer's disease (hereafter, AD) and to investigate the evolution of these subjects over time. The inputs of our approach are the electroencephalograms (hereafter, EEGs) of the patients to analyze, performed at a certain time and, again, 3 months later. Given an EEG of a subject, our approach constructs a network with nodes that represent the electrodes and edges that denote connections between electrodes. Then, it applies several network-based techniques allowing the investigation of subjects with MCI and AD and the analysis of their evolution over time. (i) A connection coefficient, supporting experts to distinguish patients with MCI from patients with AD; (ii) A conversion coefficient, supporting experts to verify if a subject with MCI is converting to AD; (iii) Some network motifs, i.e., network patterns very frequent in one kind of patient and absent, or very rare, in the other. Patients with AD, just by the very nature of their condition, cannot be forced to stay motionless while undergoing examinations for a long time. EEG is a non-invasive examination that can be easily done on them. Since AD and MCI, if prodromal to AD, are associated with a loss of cortical connections, the adoption of network analysis appears suitable to investigate the effects of the progression of the disease on EEG. This paper confirms the suitability of this idea Graphical Abstract Ability of our proposed model to distinguish a control subject from a patient with MCI and a patient with AD. Blue edges represent strong connections among the corresponding brain areas; red edges denote middle connections, whereas green edges indicate weak connections. In the control subject (at the top), most connections are blue. In the patient with MCI (at the middle), most connections are red and green. In the patient with AD (at the bottom), most connections are either absent or green. . [ABSTRACT FROM AUTHOR]

A classical result, due to Bollobás and Thomason, and independently Komlós and Szemerédi, states that there is a constant C such that every graph with average degree at least C k 2 has a subdivision of K k , the complete graph on k vertices. We study two directions extending this result. • Verstraëte conjectured that a quadratic bound guarantees in fact two vertex-disjoint isomorphic copies of a K k -subdivision. • Thomassen conjectured that for each k ∈ N there is some d = d (k) such that every graph with average degree at least d contains a balanced subdivision of K k. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on d (k) remains open. In this paper, we show that a quadratic lower bound on average degree suffices to force a balanced K k -subdivision. This gives the right order of magnitude of the optimal d (k) needed in Thomassen's conjecture. Since a balanced K m k -subdivision trivially contains m vertex-disjoint isomorphic K k -subdivisions, this also confirms Verstraëte's conjecture in a strong sense. [ABSTRACT FROM AUTHOR]

We say that a graph G is Ramsey for H1 versus H2 and write G - (H1,H2) if every red-blue coloring of the edges of G contains either a red copy of H1 or a blue copy of H2. In this paper we study the threshold for the event that the ... [ABSTRACT FROM AUTHOR]

In this paper we propose a new notion of a clique reliability. The clique reliability is understood as the ratio of the number of statistically significant links in a clique to the number of edges of the clique. This notion relies on a recently proposed original technique for separating inferences about pairwise connections between vertices of a network into significant and admissible ones. In this paper, we propose an extension of this technique to the problem of clique detection. We propose a method of step-by-step construction of a clique with a given reliability. The results of constructing cliques with a given reliability using data on the returns of stocks included in the Dow Jones index are presented. [ABSTRACT FROM AUTHOR]

This study explores the evolution of institutional collaborations in articles published in the Strategic Management Journal between 1980 and 2014 via descriptive analysis and social network analysis. These analyses show that, in each sub-period, the number of institutions involved, as measured by papers published, increased significantly and a significant number of new institutions participated in the strategic management community via the SMJ. However, a few institutions from the US dominated the field. The collaboration network was weakly clustered, fragmented, and scattered, and the relationship among institutions was not close. International collaborations have been growing based on center-periphery, international trade, and social factors, instead of geographic proximity. An inclusive evaluation of the results, limitations, and suggestions for future research is provided. [ABSTRACT FROM AUTHOR]

SUMMARY The quasi-average mean square consensus problem for wireless sensor networks is studied in this paper. The related networks considered are time continuous and linear, and possess the leader-follower structures in which some sensors act as leaders and the others act as followers, with the locale information controlled. Three different leader-follower structures are proposed in this paper. The first one is the topology with fixed leaders and varying followers which arrives at a quasi-average mean square consensus by applying the sleeping-awaking method to all cliques of the followers. The second one is the topology with fixed leaders and fixed followers which arrives at a quasi-average value consensus via the general protocol. The third one is the topology with varying leaders and fixed followers which arrives at a quasi-average mean square consensus by applying the sleeping-awaking method to all cliques of the leaders. For mentioned three topologies, some necessity and sufficiency conditions of the related consensus are obtained, respectively. To illustrate the effectiveness of the obtained results, some numerical examples are presented finally. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The paper is dealing with scanpath comparison of eye-tracking data recorded during case study focused on the evaluation of 2D and 3D city maps. The experiment contained screenshots from three map portals. Two types of maps were used - standard map and 3D visualization. Respondents' task was to find particular point symbol on the map as fast as possible. Scanpath comparison is one group of the eye-tracking data analyses methods used for revealing the strategy of the respondents. In cartographic studies, the most commonly used application for scanpath comparison is eyePatterns that output is hierarchical clustering and a tree graph representing the relationships between analysed sequences. During an analysis of the algorithm generating a tree graph, it was found that the outputs do not correspond to the reality. We proceeded to the creation of a new tool called ScanGraph. This tool uses visualization of cliques in simple graphs and is freely available at www.eyetracking.upol.cz/scangraph. Results of the study proved the functionality of the tool and its suitability for analyses of different strategies of map readers. Based on the results of the tool, similar scanpaths were selected, and groups of respondents with similar strategies were identified. With this knowledge, it is possible to analyse the relationship between belonging to the group with similar strategy and data gathered from the questionnaire (age, sex, cartographic knowledge, etc.) or type of stimuli (2D, 3D map). [ABSTRACT FROM AUTHOR]

Copyright of Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Organizations join interorganizational networks in the hope of gaining exposure to learning opportunities, and accessing valuable extramural resources and knowledge. In this paper we argue that participation in interorganizational networks also reduces performance differentials among organizational nodes. We examine three alternative mechanisms capable of sustaining this prediction. The first (strength of ties) operates at a strictly local level defined in terms of dyadic relations linking organizations. The second mechanism (social proximity) operates at an intermediate - or meso level of interdependence defined in terms of membership in overlapping cliques into which interorganizational networks are typically organized. The third mechanism (structural equivalence) is global and pertains to jointly occupied network positions. The objective of this paper is to examine at which of these levels network effects operate to reduce performance differentials among members of interorganizational networks. Our empirical analysis of performance differentials between hospitals in a regional community supports the following conclusions: (i) performance spillover effects are highly differentiated and vary significantly across network levels; (ii) organizations occupying similar positions within the network are more similar in terms of performance; (iii) joint membership in multiple sub-groups (or cliques) reduces performance differentials up to a limit; after this limit is reached, the performance of organizational partners begins to diverge; (iv) the strength of direct collaboration between organizational partners does not necessarily reduce interorganizational performance differentials. The results of the study are new because available research on interorganizational networks says little about the range of network effects, i.e., about how far the performance spillover effects that operate through networks propagate throughout organizational fields and communities. These results are also consequential because they suggest that network effects on performance differentials are sensitive to the specification of network boundaries. [ABSTRACT FROM AUTHOR]

Quarantine measures are one of the first lines of defense against the spread of infectious diseases. However, maintaining these measures over extended periods can be challenging due to a phenomenon known as quarantine fatigue. In this paper, we investigate the impact of quarantine fatigue on the spread of infectious diseases by using an epidemic model on random networks with cliques. In our model, susceptible individuals can be quarantined up to n times, after which they stop complying with quarantine orders due to fatigue. Our results show that quarantine fatigue may induce a regime in which increasing the probability of detecting and isolating infected individuals (along with their close contacts) could subsequently increase the expected number of cases at the end of an outbreak. Moreover, we observe that quarantine fatigue can trigger an abrupt phase transition at the critical reproduction number R 0 = 1. Finally, we explore a scenario where a non-negligible number of individuals are infected at the beginning of an epidemic, and our results show that, depending on the value of n , an abrupt transition between a controlled epidemic and a large epidemic event can occur for R 0 < 1. • We study an epidemic model with quarantine fatigue. • Quarantine fatigue can induce an abrupt epidemic phase transition. • Our model exhibits a backward bifurcation phenomenon. [ABSTRACT FROM AUTHOR]

Community detection has attracted a great deal of attention in recent years. A parsimony criterion for detecting this structure means that as minimal as possible number of inserted and deleted edges is needed when we make the network considered become a disjoint union of cliques. However, many small groups of nodes are obtained by directly using this criterion to some networks especially for sparse ones. In this paper we propose a weighted parsimony model in which a weight coefficient is introduced to balance the inserted and deleted edges to ensure the obtained subgraphs to be reasonable communities. Some benchmark testing examples are used to validate the effectiveness of the proposed method. It is interesting that the weight here can be determined only by the topological features of the network. Meanwhile we make some comparison of our model with maximizing modularity Q and modularity density D on some of the benchmark networks, although sometimes too many or a little less numbers of communities are obtained with Q or D, a proper number of communities are detected with the weighted model. All the computational results confirm its capability for community detection for the small or middle size networks. [ABSTRACT FROM AUTHOR]

This paper outlines issues concerning collaboration, group behaviour, complexity and organisations with some reference to specific events organised by the Embracing Complexity in Design (ECiD) project of the D21C AHRC and EPSRC UK research Cluster. These events aimed to encourage emergence in transdisciplinary areas dealing with design research, complexity, media art with live or participatory elements and new media. They involved group work in a performative context along with on-line proceedings. The authors' research perspectives in art-design-technology, performance art and collaboration informed the paper, which explores possible prerequisites and conditions that stimulate or inhibit emergent behaviour among groups of creative individuals, drawing upon concepts from the fields of Complexity Theory and the Social Sciences. Suggestions, terse statements, open ends and partial completion are integral to the emerging nature of the research outlined, although a tentative framework is proposed in which to position work observed. Some recommendations are made to provide pointers for further academic and practice-based work. [ABSTRACT FROM AUTHOR]

The suggestion that new courses can be constructed from existing learning objects appears technically self-evident but remains unproven. Despite increasing evidence that learning objects can provide a suitable structure for constructing courses most evidence is based on creating learning objects, either through restructuring existing materials or as a set of newly created learning objects. There is little evidence for building a new course from existing learning objects where any significant number of these have been developed for a different course elsewhere. Authors who adopt a constructivist model of knowledge might view this lack of evidence as confirmation of the inherent difficulty of integrating resources created within different communities. Those following a scientific model of knowledge would view this as a temporary problem that will be resolved when a sufficient volume of materials exists in repositories. This paper argues that reconfiguration of learning objects to create new courses is significantly more complex than is currently recognized, even within a scientific framework of knowledge. By implication, far more research is needed to understand reconfiguration and re-integration than initial ‘creation’. [ABSTRACT FROM AUTHOR]

For a finite simple group G and G-conjugacy class of elements of order 3, X. The A4-graph is defined as a simple graph denoted by A4(G, X) possess the vertex set X and x, y ∈ X are adjacent, if and only if x ≠ y and xy-1 = yx-1. In this paper, we investigate the structure of A4(G, X) when G is one of the Mathieu groups. [ABSTRACT FROM AUTHOR]

Graph models have long been used in social network analysis and other social and natural sciences to render the analysis of complex systems easier. In applied studies, to understand the behaviour of social networks and the interactions that command that behaviour, it is often necessary to identify sets of elements which form cohesive groups, i.e., groups of actors that are strongly interrelated. The clique concept is a suitable representation for groups of actors that are all directly related pair-wise. However, many social relationships are established not only face-to-face but also through intermediaries, and the clique concept misses all the latter. To deal with these cases, it is necessary to adopt approaches that relax the clique concept. In this paper we introduce a new clique relaxation-the triangle k-club-and its associated maximization problem-the maximum triangle k-club problem. We propose integer programming formulations for the problem, stated in different variable spaces, and derive valid inequalities to strengthen their linear programming relaxations. Computational results on randomly generated and real-world graphs, with $$k=2$$ and $$k=3$$ , are reported. [ABSTRACT FROM AUTHOR]

A cover-grammar of a finite language is a context-free grammar that accepts all words in the language and possibly other words that are longer than any word in the language. In this paper, we describe an efficient algorithm aided by Ant Colony System that, for a given finite language, synthesizes (constructs) a small covergrammar of the language. We also check its ability to solve a grammatical inference task through the series of experiments. [ABSTRACT FROM AUTHOR]

Assume that G is a finite group and X is a subset of G. The commuting graph is denoted by С(G,X) and has a set of vertices X with two distinct vertices x, y € X, being connected together on the condition of xy = yx. In this paper, we investigate the structure of Ϲ(G,X) when G is a particular type of Leech lattice groups, namely Higman–Sims group HS and Janko group J2, along with X as a G-conjugacy class of elements of order 3. We will pay particular attention to analyze the discs’ structure and determinate the diameters, girths, and clique number for these graphs. [ABSTRACT FROM AUTHOR]

Combinatorial threshold-linear networks (CTLNs) are a special class of recurrent neural networks whose dynamics are tightly controlled by an underlying directed graph. Recurrent networks have long been used as models for associative memory and pattern completion, with stable fixed points playing the role of stored memory patterns in the network. In prior work, we showed that target-free cliques of the graph correspond to stable fixed points of the dynamics, and we conjectured that these are the only stable fixed points possible [19,8]. In this paper, we prove that the conjecture holds in a variety of special cases, including for networks with very strong inhibition and graphs of size n ≤ 4. We also provide further evidence for the conjecture by showing that sparse graphs and graphs that are nearly cliques can never support stable fixed points. Finally, we translate some results from extremal combinatorics to obtain an upper bound on the number of stable fixed points of CTLNs in cases where the conjecture holds. [ABSTRACT FROM AUTHOR]

The principal component analysis is a well-known and widely used technique to determine the essential dimension of a data set. Broadly speaking, it aims to find a low-dimensional linear manifold that retains a large part of the information contained in the original data set. It may be the case that one cannot approximate the entirety of the original data set using a single low-dimensional linear manifold even though large subsets of it are amenable to such approximations. For these cases we raise the related but different challenge (problem) of locating subsets of a high dimensional data set that are approximately 1-dimensional. Naturally, we are interested in the largest of such subsets. We propose a method for finding these 1-dimensional manifolds by finding cliques in a purpose-built auxiliary graph. [ABSTRACT FROM AUTHOR]

We study a random graph model in continuous time. Each vertex is partially copied with the same rate, i.e. an existing vertex is copied and every edge leading to the copied vertex is copied with independent probability p. In addition, every edge is deleted at constant rate, a mechanism which extends previous partial duplication models. In this model, we obtain results on the degree distribution, which shows a phase transition such that either -- if p is small enough -- the frequency of isolated vertices converges to 1, or there is a positive fraction of vertices with unbounded degree. We derive results on the degrees of the initial vertices as well as on the sub-graph of non-isolated vertices. In particular, we obtain expressions for the number of star-like subgraphs and cliques. [ABSTRACT FROM AUTHOR]

Cooperative relaying techniques are known to provide spatial diversity for wireless fading channels. In contrast to non-cooperative transmission (direct transmission), they increase link reliability, provide higher capacity, reduce transmit power, and extend transmission range. Mostly the gains of cooperative relaying are shown for single flow scenarios in the absence of inter-flow interference. In this paper we study the effect of inter-flow interference on the capacity of cooperative networks in multi-hop multi-flow settings. We used the conflict graph to model the interference and find the additional constraints introduced due to cooperative transmission by using the concept of cliques on the conflict graph, which can be used to capture the interference relation among links. We formulated the multi-commodity flow problem for network capacity using linear programming, and employed a clique based analysis of the conflict graph to compute interference constraints. It is observed that the throughput drops significantly when cooperative transmissions are used in the network. We also found that the hop counts increase when cooperative links are used that is due to avoiding interfering links, which results in losing the benefits of shortest-path routing. [ABSTRACT FROM AUTHOR]

Different social processes give rise to network structures with distinctive properties. In this paper our goal is to identify the social processes that give rise to distinct network structures (specifically, subgroups). We examine particular structural meta-relations by identifying the properties of individuals associated with specific subgroups. Clues to the process of group formation and the context in which these groups form and persist may be extracted from the properties of individuals in those groups. Following this intuition, we propose a general technique for identifying systematic patterns of attribute occupancy to determine how individual attributes may drive group formation. To connect the social context in which groups form to their structural signatures, we relate subgroup composition to nodal attributes. We illustrate the utility of comparing subgroup (e.g., clique, n-clique, k-core, etc.) co-membership with nodal co-membership in a variety of attributes. The correlations between these two co-membership matrices illustrate clearly the strength of association between shared attributes and shared subgraph membership. Furthermore, examining these correlations across groups of different sizes indicates where these attributes are most strongly associated with group co-membership. Additionally, these correlations fit well into a QAP framework to determine where shared subgraph membership has a stronger (or weaker) relation to shared attribute membership than we would expect by chance. We demonstrate the technique with a series of large, online friendship networks on the order of thousands of nodes to illustrate how factors such as gender, cohort, residence, and other attributes are associated with co-membership across a range of clique sizes. [ABSTRACT FROM AUTHOR]

Spatial separation in located services and activities is often essential. Examples include homeland security, military asset defense, impacts on the environment, franchise outlet location, and promoting public wellbeing. When planning and management is supported by mathematical modeling, a difficulty has been efficient representation of spatial separation conditions. This paper reviews an optimization model, the anti-covering location problem, used to support planning and management problems where spatial separation must be ensured between sited services/activities. An approach is presented for the efficient and effective identification and use of spatial separation conditions called cliques in this model based upon the use of a geographic information system (GIS). Results highlight the significance of the developed methodology in terms of computational requirements, tractability and effectiveness. This research enhances capabilities for addressing important practical planning problems. [ABSTRACT FROM AUTHOR]

The aim of Air Traffic Flow Management (ATFM) is to enhance the capacity of the airspace while satisfying Air Traffic Control constraints and airlines requests to optimize their operating costs. This paper presents a design of a new route network that tries to optimize these criteria. The basic idea is to consider direct routes only and vertically separate intersecting ones by allocating distinct flight levels, thus leading lo a graph coloring problem. This problem is solved using constraint programming after having found large cliques with a greedy algorithm. These cliques are used to post global constraints and guide the search strategy. With an implementation using FaCiLe. our Functional Constraint Library, optimality is achieved for all instances except the largest one. while the corresponding number of flight levels could fit in the current airspace structure. This graph coloring technique has also been tested on various benchmarks, featuring good results on real-life instances, which systematically appear to contain large cliques. [ABSTRACT FROM AUTHOR]

In this paper, to find all maximal cliques of a trapezoid graph a set of intervals have been constructed by projecting the geometrical representation of the graph on the bottom line. The proposed algorithm for this purpose takes O( n 2 +γ n ) time, where n is the number of vertices of the graph and γ is the output size. [ABSTRACT FROM AUTHOR]

A characteristic common to several problems of molecular biology consists in the satisfaction of a set of constraints coming from different sources of biological knowledge. In this paper, we present two problems that take advantage of a constraint satisfaction formulation. The first problem deals with the representation and visualization of RNA secondary structures. The program RNASEARCH implements an original backtracking based algorithm that evaluates at each node the satisfaction of spatial constraints with the aim at drawing a representation without overlap between secondary structural elements. The second problem addresses the determination of RNA secondary structure in accordance with data. With the program SAPSSARN, the application of classic filtering algorithm is used and we discuss a new search algorithm which computes only so called saturated secondary structures. The main result certainly is the possibility to relax the constraint of the absence of secondary structural elements forbidden in secondary structures computed with dynamic programming based approaches: pseudoknots. Finally, we show how each program takes advantage from the other through a protocol driven by constraints. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of nonprofit organizations—the organizational infrastructure of civil society—in East Central Europe, from one important respect: by placing them in the context of the comparative historical sociology of the region's widespread informality. This involves two steps: (1) summarizing an argument about the role of informality in East Central European capitalism today in order to (2) outline its implications for the study of post-state-socialist nonprofits. Most of the empirical examples come from Hungary. These examples serve illustrative purposes and are intended as devices to provoke new analysis. They are meant to open, rather than close, discussion. [ABSTRACT FROM AUTHOR]

D. Cvetković, M. Doob and H. Sachs considered the high order eigenvalue problems of graphs. The high order eigenvalues of a graph G are solutions of the high degree homogeneous polynomial equations derived from G. We propose the adjacency tensor A (G) of a graph G and show that the high order eigenvalues of G can be regarded as eigenvalues of A (G). Some results of the spectrum of the adjacency matrix are extended to the spectrum of A (G) by using the spectral theory of nonnegative tensors. An upper bound of chromatic number is given via the spectral radius of A (G). Our upper bound is a generalization of Wilf's bound χ (G) ≤ ρ (G) + 1 (where ρ (G) is the spectral radius of the adjacency matrix of a graph G) and sharper than the bound of Wilf in some classes of graphs. A formula of the number of cliques of fixed size which involve the spectrum of A (G) is obtained. [ABSTRACT FROM AUTHOR]

The clique‐chromatic number of a graph is the minimum number of colors required to assign to its vertex set so that no inclusion maximal clique is monochromatic. McDiarmid, Mitsche, and Prałat proved that the clique‐chromatic number of the binomial random graph Gn,12 $G\left(n,\frac{1}{2}\right)$ is at most 12+o(1)log2n $\left(\frac{1}{2}+o(1)\right){\mathrm{log}}_{2}n$ with high probability (whp). Alon and Krivelevich showed that it is greater than 12000log2 n $\frac{1}{2000}{\mathrm{log}}_{2}\unicode{x0200A}n$ whp and suggested that the right constant in front of the logarithm is 12 $\frac{1}{2}$. We prove their conjecture and, beyond that, obtain a tight concentration result: whp χcGn,12=12log2 n−Θ(ln ln n) ${\chi }_{c}\left(G\left(n,\frac{1}{2}\right)\right)=\frac{1}{2}{\mathrm{log}}_{2}\unicode{x0200A}n-{\rm{\Theta }}(\mathrm{ln}\unicode{x0200A}\mathrm{ln}\unicode{x0200A}n)$. [ABSTRACT FROM AUTHOR]

This paper presents a network evolution model, which is based on the clustering approach. The proposed approach depicts the network evolution, which demonstrates the network formation from individual nodes to fully evolved network. An agglomerative hierarchical clustering method is applied for the evolution of network. In the paper, we present three case studies which show the evolution of the networks from the scratch. These case studies include: terrorist network of 9/11 incidents, terrorist network of WMD (Weapons Mass Destruction) plot against France and a network of tweets discussing a topic. The network of 9/11 is also used for evaluation, using other social network analysis methods which show that the clusters created using the proposed model of network evolution are of good quality, thus the proposed method can be used by law enforcement agencies in order to further investigate the criminal networks

Analysis of insurance data provides input for making decisions regarding underwriting, pricing of insurance products, and claims, as well as profitability analysis. In this paper, we consider graphical modeling as a vehicle to reveal dependency structure of categorical variables used in the Australian Automobile data. The methodology developed here may supplement the traditional approach to ratemaking. Topics considered are the description of the automobile data set, preprocessing of the variables, visualization tools suitable for contingency tables, classical test of independence, loglinear models, the concept of conditional independence, and graphical modeling as a vehicle to explore the dependency structure among categorical variables, as well as a review of frequency rates by rating class. [ABSTRACT FROM AUTHOR]