Strong cliques in diamond-free graphs Chiarelli, Nina; Martínez-Barona, Berenice; Milanič, Martin ...
Theoretical computer science,
02/2021, Volume:
858
Journal Article
Peer reviewed
Open access
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of ...diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or co-NP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?
On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.
•A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets.•We study strong cliques in the class of diamond-free graphs.•We characterize diamond-free CIS graphs and study their Erdős-Hajnal property.•We characterize co-strongly perfect diamond-free graphs.•We derive hardness results for five related problems.
Bovine tuberculosis (bTB) is a chronic respiratory infectious disease of domestic livestock caused by intracellular
infection, which causes ~$3 billion in annual losses to global agriculture. ...Providing novel tools for bTB managements requires a comprehensive understanding of the molecular regulatory mechanisms underlying the
infection. Nevertheless, a combination of different bioinformatics and systems biology methods was used in this study in order to clearly understand the molecular regulatory mechanisms of bTB, especially the immunomodulatory mechanisms of
infection.
RNA-seq data were retrieved and processed from 78 (39 non-infected control vs. 39
-infected samples) bovine alveolar macrophages (bAMs). Next, weighted gene co-expression network analysis (WGCNA) was performed to identify the co-expression modules in non-infected control bAMs as reference set. The WGCNA module preservation approach was then used to identify non-preserved modules between non-infected controls and
-infected samples (test set). Additionally, functional enrichment analysis was used to investigate the biological behavior of the non-preserved modules and to identify bTB-specific non-preserved modules. Co-expressed hub genes were identified based on module membership (MM) criteria of WGCNA in the non-preserved modules and then integrated with protein-protein interaction (PPI) networks to identify co-expressed hub genes/transcription factors (TFs) with the highest maximal clique centrality (MCC) score (hub-central genes).
As result, WGCNA analysis led to the identification of 21 modules in the non-infected control bAMs (reference set), among which the topological properties of 14 modules were altered in the
-infected bAMs (test set). Interestingly, 7 of the 14 non-preserved modules were directly related to the molecular mechanisms underlying the host immune response, immunosuppressive mechanisms of
, and bTB development. Moreover, among the co-expressed hub genes and TFs of the bTB-specific non-preserved modules, 260 genes/TFs had double centrality in both co-expression and PPI networks and played a crucial role in bAMs-
interactions. Some of these hub-central genes/TFs, including
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
, and
, had potential targets for inducing immunomodulatory mechanisms by
to evade the host defense response.
The present study provides an in-depth insight into the molecular regulatory mechanisms behind
infection through biological investigation of the candidate non-preserved modules directly related to bTB development. Furthermore, several hub-central genes/TFs were identified that were significant in determining the fate of
infection and could be promising targets for developing novel anti-bTB therapies and diagnosis strategies.
It is an important challenge to detect an overlapping community and its evolving tendency in a complex network. To our best knowledge, there is no such an overlapping community detection method that ...exhibits high normalized mutual information (NMI) and <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula>-score, and can also predict an overlapping community's future considering node evolution, activeness, and multiscaling. This paper presents a novel method based on node vitality, an extension of node fitness for modeling network evolution constrained by multiscaling and preferential attachment. First, according to a node's dynamics such as link creation and destruction, we find node vitality by comparing consecutive network snapshots. Then, we combine it with the fitness function to obtain a new objective function. Next, by optimizing the objective function, we expand maximal cliques, reassign overlapping nodes, and find the overlapping community that matches not only the current network but also the future version of the network. Through experiments, we show that its NMI and <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula>-score exceed those of the state-of-the-art methods under diverse conditions of overlaps and connection densities. We also validate the effectiveness of node vitality for modeling a node's evolution. Finally, we show how to detect an overlapping community in a real-world evolving network.
This study is designed to explore hub genes participating in colorectal cancer (CRC) development through weighted gene co-expression network analysis (WGCNA).
Expression profiles of CRC and normal ...samples were retrieved from the Gene Expression Omnibus (GEO) and the Cancer Genome Atlas (TCGA), and were subjected to WGCNA to filter differentially expressed genes with significant association with CRC. Functional enrichment analysis and protein-protein interaction (PPI) analysis were carried out to filter the candidate genes, further and survival analysis was performed for the candidate genes to obtain potential regulatory hub genes in CRC. Expression analysis was conducted for the candidate genes and a multifactor model was established.
After differential analysis and WGCNA, 289 candidate genes were filtered from the GEO and TCGA. Further functional enrichment analysis demonstrated possible regulatory pathways and functions. PPI analysis filtered 15 hub genes and survival analysis indicated a significant correlation of CLCA1, CLCA4, and CPT1A with prognosis of patients with CRC. The multifactor Cox risk model established based on the three genes revealed that if the three genes were a gene set, they had well predictive capacity for the prognosis of patients with CRC.
CLCA1, CLCA4, and CPT1A express at low levels in CRC and function as core anti-tumor genes. As a gene set, they can predict prognosis well.
•We propose a memory efficient method, CMC-bit, for maximal clique enumeration on real-world sparse graphs.•We use an efficient order strategy to reduce both the CPU cost in the candidate map ...construction and to decrease the candidate clique number.•The method has a stable total execution time and suits well in memory-limited scenarios.•We devise a parallel implementation of CMC-bit based on MapReduce.•The method is faster than baselines on real world datasets and its parallel implementation is scalable.
Maximal clique enumeration (MCE) is a widely studied problem that plays a crucial role in structure mining of undirected graphs. The increasing scale of real-world graphs has brought the challenges of high memory cost and high CPU workload to the problem. In this paper, we propose a memory efficient method named CMC-bit for MCE on sparse graphs. It reduces the memory cost via minimizing the candidate cliques and representing them by the data structure bitset. It generates an appropriate order for the vertex set according to two optimized principles to reduce the CPU cost. We further design a partition-based CMC-bit algorithm with a one-side extending strategy to solve the memory-limited problem. We parallelize the CMC-bit algorithm based on MapReduce with a range-based partition strategy to make an optimal trade-off between the shuffling workload of graph decomposition and load balance in the Reduce phase. We conduct extensive experiments on 30 real-world datasets. The results demonstrate that both the CMC-bit algorithm and its parallel implementation significantly outperform the respective state-of-the-art algorithms in speed. We also show that the parallel CMC-bit algorithm achieves good performance on the scalability with respect to both the reducer number and the CPU number.
Border bases for lattice ideals Boffi, Giandomenico; Logar, Alessandro
Journal of symbolic computation,
March-April 2017, 2017-03-00, Volume:
79
Journal Article
Peer reviewed
Open access
The main ingredient to construct an O-border basis of an ideal I⊆Kx1,…,xn is the order ideal O, which is a basis of the K-vector space Kx1,…,xn/I. In this paper we give a procedure to find all the ...possible order ideals associated with a lattice ideal IM (where M is a lattice of Zn). The construction can be applied to ideals of any dimension (not only zero-dimensional) and shows that the possible order ideals are always in a finite number. For lattice ideals of positive dimension we also show that, although a border basis is infinite, it can be defined in finite terms. Furthermore we give an example which proves that not all border bases of a lattice ideal come from Gröbner bases. Finally, we give a complete and explicit description of all the border bases for ideals IM in case M is a 2-dimensional lattice contained in Z2.
We consider a hybrid flowshop scheduling problem that includes parallel unrelated discrete machines or batch processing machines in different stages of a production system. The problem is motivated ...by a bottleneck process within the production system of a transformer producer located in the Netherlands. We develop an integer programming model that minimises the total tardiness of jobs over a finite planning horizon. Our model is applicable to a wide range of production systems organised as hybrid flowshops. We strengthen our integer program by exploiting the special properties of some constraints in our formulation. We develop a decision support system (DSS) based on our proposed optimisation model. We compare the results of our initial optimisation model with an improved formulation as well as with a heuristic that was in use at the company before the implementation of our DSS. Our results show that the improved optimisation model significantly outperforms the heuristic and the initial optimisation model in terms of both the solution time and the strength of its linear programming relaxation.
Mining cohesive subgraphs from a network is a fundamental problem in network analysis. Most existing cohesive subgraph models are mainly tailored to unsigned networks. In this paper, we study the ...problem of seeking cohesive subgraphs in a signed network, in which each edge can be positive or negative, denoting friendship or conflict, respectively. We propose a novel model, called maximal <inline-formula><tex-math notation="LaTeX">(\alpha, k)</tex-math> <mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>α</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="wang-ieq1-2904569.gif"/> </inline-formula>-clique, that represents a cohesive subgraph in signed networks. Specifically, a maximal <inline-formula><tex-math notation="LaTeX">(\alpha, k)</tex-math> <mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>α</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="wang-ieq2-2904569.gif"/> </inline-formula>-clique is a clique in which every node has at most <inline-formula><tex-math notation="LaTeX">k</tex-math> <mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="wang-ieq3-2904569.gif"/> </inline-formula> negative neighbors and at least <inline-formula><tex-math notation="LaTeX">\lceil \alpha k \rceil</tex-math> <mml:math><mml:mrow><mml:mo>⌈</mml:mo><mml:mi>α</mml:mi><mml:mi>k</mml:mi><mml:mo>⌉</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="wang-ieq4-2904569.gif"/> </inline-formula> positive neighbors (<inline-formula><tex-math notation="LaTeX">\alpha \geq 1</tex-math> <mml:math><mml:mrow><mml:mi>α</mml:mi><mml:mo>≥</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="wang-ieq5-2904569.gif"/> </inline-formula>). We show that the problem of enumerating all maximal <inline-formula><tex-math notation="LaTeX">(\alpha, k)</tex-math> <mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>α</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="wang-ieq6-2904569.gif"/> </inline-formula>-cliques in a signed network is NP-hard. To enumerate all maximal <inline-formula><tex-math notation="LaTeX">(\alpha, k)</tex-math> <mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>α</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="wang-ieq7-2904569.gif"/> </inline-formula>-cliques efficiently, we first develop an elegant signed network reduction technique to significantly prune the signed network. Then, we present an efficient branch and bound enumeration algorithm with several carefully-designed pruning rules to enumerate all maximal <inline-formula><tex-math notation="LaTeX">(\alpha, k)</tex-math> <mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>α</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="wang-ieq8-2904569.gif"/> </inline-formula>-cliques in the reduced signed network. In addition, we also propose an efficient algorithm with three novel upper-bounding techniques to find the maximum <inline-formula><tex-math notation="LaTeX">(\alpha, k)</tex-math> <mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>α</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="wang-ieq9-2904569.gif"/> </inline-formula>-clique in a signed network. The results of extensive experiments on five large real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms.
Community detection in the social networks is one of the most important tasks of social computing. Highly relevant researches indicate that the social network generally contains both an overlapping ...and hierarchical structure. This paper introduces an efficient and functional community detection algorithm MOHCC, which can concurrently discover overlapping and hierarchical organization in complex networks. This algorithm first extracts all maximal cliques from the original complex network. Merges all extracted maximal cliques into a dendrogram by using the aggregative framework presented in MOHCC. Finally, it cuts through the dendrogram and obtains a network partition with maximum extended partition density. Experimental results utilizing computer-generated artificial networks and real-world social benchmark networks give satisfactory correspondence.
•Introduce the coupling strength of two neighboring communities.•A common architecture for detecting both overlapping and hierarchical organization.•Propose the extended partition density and MOHCC algorithm.•Conduct satisfactory experiments.
•New state-of-the-art exact clique enumeration algorithm for small and middle-size graphs.•Efficient pivoting rule combined with a bit-parallel encoding.•Improved preconditioning: nodes are sorted ...according to degree.
The maximal clique enumeration (MCE) problem has numerous applications in biology, chemistry, sociology, and graph modeling. Though this problem is well studied, most current research focuses on finding solutions in large sparse graphs or very dense graphs, while sacrificing efficiency on the most difficult medium-density benchmark instances that are representative of data sets often encountered in practice. We show that techniques that have been successfully applied to the maximum clique problem give significant speed gains over the state-of-the-art MCE algorithms on these instances. Specifically, we show that a simple greedy pivot selection based on a fixed maximum-degree first ordering of vertices, when combined with bit-parallelism, performs consistently better than the theoretical worst-case optimal pivoting of the state-of-the-art algorithms of Tomita et al. Theoretical Computer Science, 2006 and Naudé Theoretical Computer Science, 2016.
Experiments show that our algorithm is faster than the worst-case optimal algorithm of Tomita et al. on 60 out of 74 standard structured and random benchmark instances: we solve 48 instances 1.2 to 2.2 times faster, and solve the remaining 12 instances 3.6 to 47.6 times faster. We also see consistent speed improvements over the algorithm of Naudé: solving 61 instances 1.2 to 2.4 times faster. To the best of our knowledge, we are the first to achieve such speed-ups compared to these state-of-the-art algorithms on these standard benchmarks.
PDF
