recent research papers on graph theory

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

• View all journals
• Explore content
• About the journal
• Publish with us
• Sign up for alerts
• Open access
• Published: 08 September 2022

Explainable artificial intelligence through graph theory by generalized social network analysis-based classifier

• Serkan Ucer 1 ,
• Tansel Ozyer 2 &
• Reda Alhajj 3 , 4 , 5  

Scientific Reports volume  12 , Article number:  15210 ( 2022 ) Cite this article

8182 Accesses

5 Citations

11 Altmetric

Metrics details

• Computational biology and bioinformatics
• Mathematics and computing

We propose a new type of supervised visual machine learning classifier, GSNAc, based on graph theory and social network analysis techniques. In a previous study, we employed social network analysis techniques and introduced a novel classification model (called Social Network Analysis-based Classifier—SNAc) which efficiently works with time-series numerical datasets. In this study, we have extended SNAc to work with any type of tabular data by showing its classification efficiency on a broader collection of datasets that may contain numerical and categorical features. This version of GSNAc simply works by transforming traditional tabular data into a network where samples of the tabular dataset are represented as nodes and similarities between the samples are reflected as edges connecting the corresponding nodes. The raw network graph is further simplified and enriched by its edge space to extract a visualizable ‘graph classifier model—GCM’. The concept of the GSNAc classification model relies on the study of node similarities over network graphs. In the prediction step, the GSNAc model maps test nodes into GCM, and evaluates their average similarity to classes by employing vectorial and topological metrics. The novel side of this research lies in transforming multidimensional data into a 2D visualizable domain. This is realized by converting a conventional dataset into a network of ‘samples’ and predicting classes after a careful and detailed network analysis. We exhibit the classification performance of GSNAc as an effective classifier by comparing it with several well-established machine learning classifiers using some popular benchmark datasets. GSNAc has demonstrated superior or comparable performance compared to other classifiers. Additionally, it introduces a visually comprehensible process for the benefit of end-users. As a result, the spin-off contribution of GSNAc lies in the interpretability of the prediction task since the process is human-comprehensible; and it is highly visual.

Similar content being viewed by others

Highly accurate protein structure prediction with AlphaFold

A guide to artificial intelligence for cancer researchers

Generic protein–ligand interaction scoring by integrating physical prior knowledge and data augmentation modelling

Introduction.

Machine learning (ML) has dominated our daily life with many real-world applications, such as healthcare decision support systems, search engine recommendation systems, and autonomous driving, among others. One of the most common tasks of ML is ‘classification’ which broadly involves two steps, training and testing. While training inspires a model from one part of the data, testing uses the remaining data to check the accuracy of the model which reflects its capability in correctly realizing the classes of new samples. The data types processed with ML are not limited to tabular form, but may exist in a wide range of forms, including multimedia. Still, tabular data may be considered the most common form of data types 1 , dominating most of the applications of ML. The main struggle of the current ML paradigm is explainability of existing ML model to naive users. While the performance of the classification accuracy increases as new models emerge, surprisingly, classification decisions become complex to be justified by humans 2 . This ‘explainability’ phenomenon limits the usage of ML models in critical real-world applications (e.g., law or traffic management) since the context of a decision is hard to be justified and explained to the end-users. Our proposed social network analysis-based visual classifier, GSNAc, aims to solve this problematic aspect of ML by introducing visual cues, both at the model and at the prediction steps.

Social networks form a specific type of network graphs used for depicting real-life paradigms in the form of ‘actors’ and their ‘interactions’ with each other in a closed ecosystem 3 . In its most primitive form, a social network consists of a finite number of nodes (called actors) connected to each other via weighted edges (a weight of one for all edges is also possible) which represent a sort of ‘social interaction’ based on some kind of social quality, e.g., ‘frequency of their coffee meetings’. A pervasive form of a social network is ‘the friendship network’, e.g., Facebook.

Social Network Analysis (SNA) is a study conducted to understand various aspects of a network in general as well as its nodes individually and in groups. For example, in a friendship network, it is possible to find the most influential node (i.e., a person) in the analyzed domain. SNA techniques are widely used in various applications from link prediction for recommending useful connections in a ‘friendship network’ to detecting fraud in a ‘financial transactions network’, among others. SNA techniques mainly include, but are not limited to, detecting node or actor centrality, community (structure) detection, edge capacity, flow, and representative selection.

An overview of our past works

For a social network, it is not always necessary for the interaction to be linked to a human activity. Indeed, various types of entities other than humans may also socialize, or the relationship between them may be interpreted as a social activity analogous to human activities. Accordingly, interactions can be defined for a broader spectrum of entities such as among genomes, mice varieties, animals, insects, fruit types, etc. In this respect, increasing interest in the SNA domain has allowed many diverse real-life phenomena to be studied. In our former works 3 , 4 , we tried to address two machine learning tasks using graph theory fundamentals: “feature reduction via SNA” and “the SNAc—classification via SNA of time-genomic datasets”, respectively. For our work described in 5 , we employed SNA techniques and studied specific data from the life sciences domain, which in general do not represent any real ‘social’ value. The techniques themselves proved to be useful in the classification of a tabular dataset. We represented genomic datasets as social network graphs, where genomes are represented as ‘actors’ (nodes) and ‘their vectorial similarity’ to other genomes together with their interaction levels form ‘edges’.

Current model and the key contributions

Following the success of the proof-of-concept of this approach, we now continue searching for an extended generalized framework that is again based on graph theory and SNA. The target involves addressing the classification of tabular datasets containing either or both numerical and categorical features. Thus, the proposed GSNAc Model is a new type of visually explainable machine learning classifier that works on tabular datasets.

Our approach (see Fig.  1 ) moderately increases the explainability of the whole classification process, since it presents a traceable visual output for each predicted sample. Besides, the ‘graph classifier model—GCM’, which sits at the heart of the classification process, is again in a social network form that makes it visualizable. Those aspects merely address the current problem posed by the most advanced current set of state-of-the-art classifiers, which is the explainability of the classification task (i.e., XAI—explainability of artificial intelligence applications). To summarize, the key aspects and contributions of the GSNAc model could be enumerated as follows:

Clarity of the method, explainable process, deterministic classifier,

Graphical interface, explainability, visual engagement,

Versatility (i.e., works well for the classification of both numerical and categorical features),

Superior or on par performance (in terms of prediction accuracy) with the well-known state-of-the-art tabular data classifiers.

The brief pipeline of the GSNAc model.

Structure of the research presented

We will present our current work by introducing the problem and the techniques that will be used to address the problem posed in “ Related work and key concepts ” section. We will then discuss details of the GSNAc Model starting with an overview in “ GSNAc: a visual supervised learner ” section. We will further detail the model in “ The data: converting tabular data to raw network graph ”, “ The model: graph enrichment and extraction of the graph classifier model ”, “ The prediction process: using visual graph classifier model (GCM) ” sections. Experiments and results of the comparison with conventional machine learning classifiers will be present in “ Experiments and results ” section. We dedicated “ Explainability of the GSNAc model ” section to elaborate on the explainability aspect of the proposed GSNAc Model. Discussion and further study are covered in “ Discussion and further work ” section.

In Appendix I , we provide the code, the detailed parameters of the classifiers & the datasets, and the runtime parameters of the GSNAc Model, including the raw performance results, and the URL to the directory of outputs GSNAc produced throughout the experiments, all for the sake of the reproducibility of the conducted research. Finally, in Appendix II , we provide the user interface and the output of GSNAc.

Related work and key concepts

Graphs, social networks, and sna.

Social networks 6 form a subtype of network graphs that originated from graph theory. Graph theory is briefly the study of network graphs, which are mathematical representations used to model pairwise relations between objects. A graph is normally characterized by a set of nodes and edges which connect nodes. Typically, edges may have a default weight of 1; alternatively, varying weights may be assigned to various edges to reflect the value of the relationship between the connected nodes. Indeed, many real-world problems and systems can be reduced and represented as a network graph. For instance, the traffic system connecting roads in an area may be reorganized as a graph where intersections and roundabouts act as nodes and edges represent roads connecting them. This way, a navigation map application may identify a possible shortest path between two locations by analyzing the graph to determine the most appropriate route based on the combination of the costs of road segments connecting some consecutive junctions.

A network graph is simply the combination of nodes and edges connecting nodes. Each edge has a source node, a target node, and a weight value showing its effect based on the criteria applied to construct the network. Assume an edge e1 between nodes a and b has weight 4, and another edge e2 between a and c has weight 3, then we conclude that a is more similar to b than c. In some cases, edges of a network graph can be directed, i.e., the direction of connection between the source node and the target node matters, e.g., in a directed graph, two edges e1 from a to b and e3 from b to a are two different edges. If the direction doesn’t matter in the domain of study, it is safer to use undirected networks.

Having originated from the social sciences domain, Social Network Analysis (SNA) is the sum of measures inspired from graph theory to analyze the relationship among social entities. Social Network analysis encompasses many measures that can be broadly grouped as:

Centrality studies for nodes

Edge analysis

Node distance-similarity methods

Community structure studies

SNA measures used in this study are node similarity analysis, edge analysis and centrality studies.

Machine learning: the classification task

It is very common to come across the results of scientific experiments involving measurements of various aspects (in other words, features) of objects in a specific domain, and at the end objects are often categorized into a limited number of cases (called classes).

In the machine learning domain, the term ‘classification’ implies the task of first learning the characteristics of a group of objects from specific classes and then predicting the correct class for some previously unseen objects forming the test data.

Any learner model follows almost the same black-box model shown in Fig.  2 . According to this generalization, it starts with the ‘Data’ box, where the dataset under study is examined in terms of quality, completeness, and complementarity of its feature space and sample data points. Tasks such as decomposition, transformation, elimination, and improvement of the feature space are some of the common methods used in this step.

Illustrative box diagram of a general machine learning classification model.

The aim of the ‘classifier model’ box is to find and describe the connection between the data and its class, by employing mathematical and statistical techniques. Finally, in the ‘Prediction’ box, the proposed model implements its technique to process data with the model presented to produce appropriate predictions. Crucially, in this step ‘benchmarking’ ensures that we assess the merit of the classifier. Here, internal and external benchmarking can be employed, i.e., ‘statistical hypothesis testing techniques’ as the internal evaluation, and comparing the performance of the proposed classifier with the state-of-the-art established models as the external evaluation.

There is no silver bullet technique for classification tasks 7 . For instance, some classification techniques may perform efficiently on biological data while may fail to produce meaningful predictions on financial data. State-of-the-art techniques for tabular data classification consider decision tree-based classifiers. Among those, notably XGBoost 8 depends on tree learning, and dominates most of the recent 9 data science competitions. Another recent and popular research is deep learning, where its main contribution is on feature space reorganization and selection. Despite the fact that deep learning could be used for classification, their effective usage is still mainly on text, image, and video data types 10 .

Machine learning and network graphs

Even though SNA techniques are widely used to solve various problems from engineering to media; machine learning classification using network graphs is a domain that has not received enough attention from the research community. In our former work described in 5 , we employed various SNA techniques to convert time-sequential genomic data into a social network and developed a classification model to predict classes. The method proved to be useful when compared to conventional algorithms, but was limited to being applied only on time-sequential data. Within this work, we aim to generalize our classification model (abbreviated as GSNAc) to an extent that the method can be applicable to numerical/categorical datasets which include class information.

The machine learning applications for the social network domain are generally centered around two topics 11 : (i) the similarity between two graphs (or subgraph matching), and (ii) the similarity of the nodes/edges in a graph. The first one aims to find a motif between possibly two different-sized graphs (in terms of nodes and edges) to deduct a result, e.g., a deduction that both graphs have similar network dynamics. Here, a recent work in this area is worth mentioning 12 . It employed graph theory techniques for text classification. In 12 , NLP researchers first convert sentences into adjacency matrices based on the co-occurrence of words, and then to graphs. The process then efficiently predicts word similarities by employing graph similarity techniques. At this point, we state that the proposed GSNAc model has no relation with this ‘inter-graph similarity’ aspect of the mentioned research domain.

On the other hand, finding possible similarities ‘within’ a graph, in terms of the similarity between nodes or edges, is a problem partially addressed by GSNAc. The ‘node classification’ problem refers to the process of propagating labels to the unlabelled nodes on a partially labeled graph by evaluating the similarity of nodes 13 , 14 . A recent research in this area (refer to 15 ) handles node classification problems by introducing graph neural networks over graphs (particularly Graph Convolutional Networks—GCNs). This approach basically learns hidden layer representations that encode both the local graph structure and features of nodes. It has been proved useful in predicting labels on some types of networks including citation networks where it predicts the type of the document. Within this context, the node classification problem partially matches the definition of the problem tackled by GSNAc; since (after converting data to a graph and after its enrichment) we also predict the class (i.e., label) of an unseen node by evaluation against labels of the training nodes. However, in comparison to the node classification problem setting, there are major challenges that GSNAc needs to deal with. First, in the node classification problem, the complete (weighted) graph (including all nodes—i.e., training and test parts) is already in place initially, making it easier to assign labels based on their topological properties based on the complete connection structure within all nodes (labeled or unlabelled). Second, node classification can predict labels iteratively by depending on known positions, possibly starting with a frequently labeled portion of the graph. We believe that these dynamics differentiate the two problems well enough. Here it is worth mentioning that the GSNAc model is actually an end-to-end machine learning classifier on its own.

To sum up, we would like to present a recent trend on converting tabular data into networks. This approach becomes pretty useful when the aim is to visualize data to get an intuition-based idea. A recent research described in 16 efficiently converts tabular data into images (rather than networks as GSNAc does), and predicts drug responses of gene expression profiles using deep learning techniques on the generated images. While this approach does not coincide with GSNAc, it shows the popularization of expressing tabular data as 2D visible graphic items, a reasonable step towards explainability of tabular learning.

GSNAc: a visual supervised learner

In this section, following the formal problem description, we will present an overview of the GSNAc model both in diagram and pseudocode formats. A detailed description of the methodology and parameter selection strategies will be covered in the following three subsections.

Problem description and naming conventions

The formal problem description of GSNAc is exactly the same as the problem definition of machine learning for the categorical classification task: given a multi-class tabular dataset with numerical and categorical features, the process involves learning from the seen data and predicting the class of unseen data. Multi-class classification refers to predicting one or more classes for each sample. Imbalanced classification refers to a classification task where the distribution of samples across the classes is skewed. In other words, most of the existing objects represent specific classes. Fortunately, GSNAc is not merely a bi-class classifier. It does not aims to work only on balanced data, it also works on imbalanced data which makes it useful on a broader spectrum of problems. A final note on the use of GSNAc is that it currently does not support regression prediction which is predicting continuous numerical values.

Before we delve into detailed descriptions of the GSNAc methodology, we would like to present (see Fig.  3 ) the ‘naming’ convention for this research. Throughout this work, for the dataset part, our preference is to call individual observations (of an experiment) as the ‘samples’, and their defining characteristics (i.e., predictors) are called ‘features’ of the samples. Categories of the results of the experiment are called ‘classes’.

(i) Tabular data converted to adjacency (similarity) matrix (ii), and graph (iii) constructed and enriched with node degrees, edge weights, and colored by communities (classes). Layout graph intuitively shows the importance of some nodes (i.e., H. Sapiens and T-Rex have the highest number of weighted connections, therefore, larger in size) and visually depicts how similar nodes are (e.g., Shark has the smallest similarity to other nodes so it is distant from the core).

After converting the dataset to a network graph, basically dataset ‘samples’ become ‘nodes’ in the graph, and dataset ‘features’ are blended into ‘edges’ of the graph. A node may have a ‘neighbor’ if there is an edge between them. Finally, the classes are represented in the network graph as the ‘communities’.

The pipeline of the GSNAc methodology is diagrammatically described in Fig.  4 . It starts with the preprocessing of raw tabular data. After data is separated into training and test parts, a raw graph is generated using only the training part of the data. This raw graph is decorated and further processed to achieve a leaner version called graph classifier model (GCM) with fewer edges and repositioned nodes.

General overview of the GSNAc model illustrated on Iris dataset.

This GCM was then employed for predicting the class of test samples using two different similarity scores. Next, we present the master pseudocode summarizing the GSNAc methodology.

In Fig.  1 we described the GSNAc Models’ process pipeline: this type of framing comes useful when proposing a novel model. In this sense, we organized the following three sections focused on the boxes of the model, namely ‘Data: Graph generation’, ‘Model: GCM Generation’ and ‘Class Prediction’.

The data: converting tabular data to raw network graph

In this subsection, we present details on how we process the dataset, turn it into a network graph and finally how we produce, and process features that belong to the graph. Topics to be covered are:

splitting the data,

preprocessing,

feature importance and selection,

computation of similarity between samples, and

generating of the raw graph.

Splitting the tabular data

After preprocessing the data, the next step is to split the dataset into training and test samples for validation purposes. We selected cross-validation (CV) as the validation method since it is the de facto standard in ML research. For CV, the full dataset is split into k folds; and the classifier model is trained using data from (k-1) folds then tested on the remaining k’th fold. Eventually, after k iterations,, average performance scores (like F1 measure or ROC) of all folds are used to benchmark the classifier model.

A crucial step of CV is selecting the right proportion between the training and test subsamples, i.e., number of folds. Determining the most appropriate number of folds k for a given dataset is still an open research question 17 , besides de facto standard for selecting k is accumulated around k = 2, k = 5, or k = 10. To address the selection of the right fold size, we have identified two priorities:

Priority 1—Class Balance: We need to consider every split of the dataset needs to be class-balanced. Since the number of class types has a restrictive effect on selecting enough similar samples, detecting the effective number of folds depends heavily on this parameter. As a result, whenever we deal with a problem which has low represented class(es), we selected k = 2.

Priority 2—High Representation: In our model, briefly, we build a network from the training subsamples. Efficient network analysis depends on the size (i.e., number of nodes) of the network. Thus, maximize training subsamples with enough representatives from each class (diversity) is our priority as much as we can when splitting the dataset. This way we can have more nodes. In brief, whenever we do not cross priority 1, we selected k = 5.

By balancing these two priorities, we select efficient CV fold size by evaluating the characteristics of each datasets in terms of their sample size and the number of different classes. The selected fold value for each dataset will be specified in the “ Experiments and results ” section. To fulfill the class balancing priority, we employed stratified sampling. In this model, each CV fold contains approximately the same percentage of samples of each target class as the complete set.

Feature space organization and preprocessing

Preprocessing starts with the handling of missing data. For this part, we preferred to omit all samples which have one or more missing feature(s). By doing this, we have focused merely on developing the model, skipping trivial concerns.

As stated earlier, GSNAc can work on datasets that may have both numerical and categorical values. To ensure proper processing of those data types, as a first step, we separate numerical and categorical features 18 . First, in order to process them mathematically, categorical (string) features are transformed into unique integers for each unique category by a technique called labelization. It is worth noting that, against the general approach, we do not use the one-hot-encoding technique for transforming categorical features, which is the method of creating dummy binary-valued features. Labelization does not generate extra features, whereas one-hot-encoding extend the number of features.

For the numerical part, as a very important stage of preprocessing, scaling 19 of the features follows. Scaling is beneficial since the features may have a very different range and this might affect scale-dependent processes like distance computation. We have two generally accepted scaling techniques which are normalization and standardization. Normalization transforms features linearly into a closed range like [0, 1], which does not affect the variation of values among features. On the other hand, standardization transforms the feature space into a distribution of values that are centered around the mean with a unit standard deviation. This way, the mean of the attribute becomes zero and the resultant distribution has a unit standard deviation. Since GSNAc is heavily dependent on vectorial distances, we do not prefer to lose the structure of the variation within features and this way our choice for scaling the features becomes normalization. Here, it is worth mentioning that all the preprocessing is applied on the training part of the data and transformed on the test data, ensuring no data leakage occurs.

Feature importance and selection

Feature Importance (FI) broadly refers to the scoring of features based on their usefulness in prediction. It is obvious that in any problem some features might be more definitive in terms of their predictive capability of the class. Moreover, a combination of some features may have a higher effect than others in total than the sum of their capacity in this sense. FI models, in general, address this type of concern. Indeed, almost all ML classification algorithms use a FI algorithm under the hood; since this is required for the proper weighting of features before feeding data into the model. It is part of any ML classifier and GSNAc. As a scale-sensitive model, vectorial similarity needs to benefit much from more distinctive features.

For computing feature importance, we preferred to use an off-the-shelf algorithm, which is a supervised ‘k-best feature selection’ 18 method. The K-best feature selection algorithm simply ranks all features by evaluating features’ ANOVA analysis against class labels. ANOVA F-value analyzes the variance between each feature and its respective class and computes F-value which is the ratio of the variation between sample means, over the variation within the samples. This way, it assigns F values as features’ importance. Our general strategy is to keep all features for all the datasets, with an exception for genomic datasets, that contain thousands of features, we practiced omitting. For this reason, instead of selecting some features, we prefer to keep all and use the importance learned at this step as the weight vector in similarity calculation.

Computation of similarity between samples and construction of the raw graph

In this step, we generate an undirected network graph G, its nodes will be the samples and its edges will be constructed using the distance metrics 20 between feature values of the samples. Distances will be converted to similarity scores to generate an adjacency matrix from the raw graph. As a crucial note, we state that since we aim to predict test samples by using G, in each batch, we only process the training samples.

In our study for constructing a graph from a dataset we defined edge weights as the inverse of the Euclidean distance between the sample vectors. Simply, Euclidean distance (also known as L2-norm) gives the unitless straight line (shortest) distance between two vectors in space. In formal terms, for f-dimensional vectors u and v , Euclidean distance is defined as:

A slightly modified use of the Euclidean distance is introducing the weights for dimensions. Recall from the discussion of the feature importance in the former sections, some features may carry more information than others. So, we addressed this factor by computing ‘a weighted’ form of L2 norm based on distance which is presented as:

where w is the n-dimensional feature importance vector and i iterates over numerical dimensions.

The use of the Euclidean distance is not proper for the categorical variables, i.e. it is ambiguous and not easy to find how much a canary’s habitat ‘sky’ is distant from a sharks’ habitat ‘sea’. Accordingly, whenever the data contains categorical features, we have changed the distance metric accordingly to L0 norm. L0 norm is 0 if categories are the same; it is 1 whenever the categories are different, i.e., between the ‘sky’ and the ‘sea’ L0 norm is 1, which is the maximum value. Following the discussion of weights for features, the L0 norm is also computed in a weighted form as \({dist\_L0}_{w}\left(u,v\right)=\sum_{f}{w}_{j}(({u}_{j}\ne {v}_{j})\to 1)\) , where j iterates over categorical dimensions.

After computing the weighted pairwise distance between all the training samples, we combine numerical and categorical parts as: \({{dist}_{w}\left(u,v\right)}^{2}={{dist\_L2}_{w}\left(u,v\right)}^{2}+ {{dist\_L0}_{w}\left(u,v\right)}^{2}\) . With pairwise distances for each pair of samples, we get a n x n square and symmetric distance matrix D, where n is the number of training samples. In matrix D, each element shows the distance between corresponding vectors.

We aim to get a weighted network, where edge weights represent the ‘closeness’ of its connected nodes. We need to first convert distance scores to similarity scores. We simply convert distances to similarities by subtracting the maximum distance on distances’ series from each element.

Finally, after removing self-loops (i.e. setting diagonal elements of A to zero), we use adjacency matrix A to generate an undirected network graph G. In this step, we delete the lower triangular part (which is symmetric to the upper triangular part) to avoid redundancy. Note that, in transition from the adjacency matrix to a graph, the existence of a (positive) similarity score between two samples u and v creates an edge between them, and of course, the similarity score will serve as the ‘vectorial weight’ of this particular edge in graph G.

The raw graph generated in this step is a ‘complete graph’: that is, all nodes are connected to all other nodes via an edge having some weight. Complete graphs are very complex and sometimes impossible to analyze. For instance, it is impossible to produce some SNA metrics such as betweenness centrality in this kind of a graph.

The model: graph enrichment and extraction of the graph classifier model

In this section, we first compute basic SNA metrics over the network graph, then decorate the raw graph with certain properties of the tabular data, and finally process edge analysis of the raw graph. To reduce the complexity and denseness of the graph, we will trim unimportant edges by considering their structure to get a subtle form of the graph which will serve as our visual classifier model.

To increase the understandability of the procedures presented, we visualized the whole process in Fig.  5 , which belongs to a biological dataset. This dataset inspired from C. Elegans Connectome ( https://commons.wikimedia.org/wiki/File:Caenorhabditis_elegans_hermaphrodite_adult-en.svg ) incorporates 279 samples over 12 features (2 categorical, 10 numerical). It has 10 (imbalanced) classes. C. Elegans is indeed a simple worm, and its whole neuron system has been extracted, filed, and widely researched in recent years 21 , 22 , 23 . This worm has exactly 302 neurons (having unique names and positions) connected to 158 muscles and organs on its body. Out of those 302 neurons, following the Connectome research 24 , non-pharynx neurons and neurons with no synaptic connections are omitted, leaving 279 somatic neurons out of the initial 302. This dataset is useful in showing the capabilities of the proposed model. We choose the ‘AY Ganglion’ feature as the class to be predicted. In this specific case, we intend to find a predictive relationship between the neurons and their connections to specific regions throughout the worm’s body.

From raw data to GCM demonstrated on C. elegans Dataset.

Graph decoration and preprocessing

Node naming.

In general, the dataset associated with classification has dedicated sample names, e.g., names of the specific neurons in Connectome dataset or CustomerID’s in Caravan Insurance dataset 25 . Usually, this potentially beneficial information is ignored during the classification. In contrast to this, for the sake of explainability, we save and assign sample names throughout our raw graph as node names.

Community partition assignment

Community detection in a network graph refers to finding partitions of the graphs (subgraphs of connected nodes) displaying similar characteristics. It is beneficial since it reveals hidden relations among nodes in a network. Inevitably, we need to incorporate community detection within the raw graph. While many algorithms have been developed to detect communities, e.g., 26 , 27 , 28 , we do skip employing them intentionally since our network is already partitioned based on the given set of classes. That is, since the raw graph is only composed of training samples, we already do know the classes they have and the communities they belong to. In this fashion, we assign classes as communities in the raw graph.

Centrality SNA metrics

Within a graph, finding how central a node is (compared to other nodes topologically) in terms of the capacity of its entropy is an important branch of SNA metrics as mentioned in “ Related work and key concepts ” section. Among other centrality metrics 3 , the most primitive is ‘degree centrality’ which refers to the number of edges connected to a given node. ‘Weighted degree’ is the improved form of degree centrality, which also considers edge weights when aggregating node connections. Despite not using centrality metrics in the GSNAc model in a predictive capacity, we still find them useful in the model to enrich the displays produced. For this purpose, we use ‘weighted degree centrality’ for scaling the size of the nodes. The latter is a visually engaging concept and gives comparative clues about the entropy capacity of a node within a graph.

Edge pruning

We already highlighted the need for removing self-loops in the former section to simplify the complexity of the raw graph. But, still, this graph is a complete graph, i.e., every node is connected to every other node leading to a graph density of 100%. Now we need to identify and further remove unimportant edges of this complete graph to ensure that our model includes only relevant and important edges; this way, its entropy increases.

Some research 29 , 30 already addressed the raffination of the so-called ‘hairball graph’ which is overly dominated by unimportant edges. We prefer to use a custom raffination at this step, keeping only at most k strongest edges for each node and dropping the remaining edges. This way, by keeping the k value small, we can achieve a raffinated, less dense version of the raw graph. Also, by only keeping the most information-bearing edges, entropy of the graph will increase.

Instead of setting a constant k value for each dataset, we have set an upper limit, and dynamically identified the value of k by analyzing the frequency of the least represented class within the population.

Edge fortification

So far, we have only described how the ‘class’ information of tabular data is only used in graph community assignments. GSNAc might incorporate class information in the model generation step, since it is a supervised model. We prefer to use this very important class information as a secondary step in a reward/loss scheme for edges. This time, we reconsider weights of the edges by analyzing classes of their endpoints. The weight of an edge is improved by a constant factor when it connects two nodes from the same class. Likewise, the same factor is used to decrease the weight of an edge when its endpoints are from different classes. After these steps, the graph may become disconnected since some nodes can lose all of their edges and become isolated, or some group of nodes can be only connected to themselves, creating an isolated connected component.

The prediction process: using visual graph classifier model (GCM)

As described in the previous sections, we have carefully constructed a vectorial similarity-based network graph, pruned its edges by their importance, and finally generated a leaner graph which will act as our classifier model named GCM. At this point, we will feed test nodes one-by-one into GCM and conduct the prediction by analyzing most similar nodes. For this similarity analysis, we have employed two complementary methods: vectorial and topological.

Adding test node to GCM

Vectorial similarities of test node to gcm nodes.

Vectorial similarity is the weighted (L2 and/or L0) distance-based similarity score already computed during the network generation phase. To calculate this vectorial similarity score for each test data to be predicted, upon normalization of test nodes vector, L2 norm-based distance for the numerical part, and L0 norm-based distance for categorical part of the test data are calculated using the same weights that were learned from the training data at step FI. These distance scores are calculated pairwise between the test node and all nodes of GCM. Following the conversion from distances to similarity scores, the test node becomes connected to all nodes of GCM via different edge weights.

Topological similarities of test node to GCM nodes

As we already have a topological structure in the form of a graph, we can also analyze the neighborhood structure of nodes. A topological similarity, in its simple form, can be calculated by comparing the neighborhood structure of two nodes: if they have the same neighborhood with similar weights, they can be considered topologically similar. Pairwise cosine similarity 31 has been used to compute the topological similarity between the test node and nodes of GCM; this measure is useful when one needs to compare two bags of words (with frequencies). Indeed, it is widely used in natural language processing for comparing text similarity.

Our usage of cosine similarity is to define a bag of words as neighborhood lists of nodes and frequencies as the weights of edges (i.e., vectorial similarity) connecting them. As can be seen in the formula, it is again a pairwise calculation as the vector product of the test node (test) and a node from GCM (v) divided by the product of L2 norms of the same vectors. Note that, the value k in the formula refers to the number of neighbors of v; it is expected to be smaller than the number of neighbors of the test node which is already connected to all nodes of GCM.

To conclude, in topological similarity, we do not only consider the direct neighbors of a node from GCM. We also compare two nodes’ neighborhood structure, i.e., how their indirect neighbors match.

Prediction strategy: assigning class to the test node

Topological similarity is somewhat dependent on vectorial similarity since the former uses edge weights (i.e., vectorial similarity) as input. However, topological similarity does not produce the same graph as vectorial similarity, and GCM built by topological similarity gives some clue about nodes’ position within the graph. In this respect, it can be used as a secondary similarity metric, complementing vectorial similarity. We have decided to blend these two similarity metrics to achieve a higher prediction performance and it turned out that using topological similarities as secondary ‘sage’ (whenever decision margin is small with vectorial similarity) has been proven beneficial for prediction as described next.

For actual prediction, we primarily use vectorial similarity and keep the maximum number of edges for a given test node from each represented class in GCM based on their weights. Our prediction is then to group and aggregate those edges class-wise to get an average similarity of the test node to each class, respectively (see Fig.  6 a). To assign a class to a test node, we only consider the top two high-ranked classes and compare their aggregated similarity scores.

( a ) Prediction Phase 1 sample diagram on C. Elegans dataset. İllustrating the prediction attempt of the test node ADFL (not displayed in the diagram). Raw list of neighbors of ADFL listed, sorted by vectorial similarity, grouped by class, and finally similarities are aggregated by class. A prediction is not made since the top two highest averaged classes have very close scores (under margin). ( b ) Prediction Phase 2 sample diagram on C. Elegans dataset. Illustrating the prediction of the test node ADFL (not displayed in the diagram). This time, the prediction is made based on topological similarity in the same fashion with the first round. This time, without seeking a distinctive margin, the top (highest topological similarity average) class is assigned as the prediction.

When the top most classes differ by a magnitude, we assign the top-ranked class to the test node. However, in case the vectorial similarity-based model fails to find two distinctively separated classes (i.e., setting a margin threshold of 1% means the difference of the scores of the top two classes must be higher than 1%) we leave the prediction completely to the secondary sage, i.e., the topological similarity (see Fig.  6 b). This time, in the same fashion, we aggregate the average similarities of the classes over topological similarities, and (without further check) we assign the top-ranked class to the test node.

Experiments and results

The datasets.

GSNAc was initially designed to work efficiently with balanced and bi-class datasets (i.e., binary classification). However, during the development, we discovered that it can effectively classifies some multiclass and imbalanced datasets, as well. As a proof of concept for GSNAc, we carefully selected as many real-world diverse datasets from various domains with various feature and class structures. We also considered including synthetic datasets as they give the chance to compare similar work by other researchers. Finally, we considered some other custom datasets compiled for this research. Table 1 summarizes the datasets used in the experiments.

In the preprocessing steps, we standardized the datasets before feeding them to the ML classifiers since some classifiers (especially those based on scale sensitive distance metrics like SVM and kNN) heavily depend on the data to be scaled. To select the standardization over other competing techniques, normalization is also needed especially for SVM RBF classifier (GSNAc’s main competitors are reported in Table 3 ) since they assume that all the features are centered around zero and variance of the data is of the same order 32 .

Experimental setup

We implemented the GSNAc Model using Python. We selected the platform of GSNAc to be compatible with python’s sklearn library 33 since it is the de facto standard platform in the ML domain. Also, it allows parameter optimization by grid or random search methods, making it useful to find the best performer set of parameters for a given task. Within this context, we did not practice parameter search or optimization for this research in order to present a fair comparison with other ML classifiers. We also used other python libraries such as networkx, bokeh, pandas, and NumPy.

Classifiers used for benchmarking

To be comprehensive and fair in the testing, we decided to include as diverse ML models as possible in terms of their approach for the classification. All the classifiers run with their default parameter set (except for ANN where the maximum number of iterations was upgraded from 200 to 2000 since it does not usually converge with 200 iterations), and likewise, we used default parameters for GSNAc, i.e., we did not search for the best parameters. We used scikit-learn 33 implementation of the utilized classifiers except xgboost, where we used the native xgboost python library 8 . We present in Table 2 the list of classifiers and their parameters used for the comparison.

Performance comparison of GSNAc with traditional tabular learners

In order to test classification efficiency of the GSNAc on the given datasets, we have investigated the comparison of SNAc with traditional machine learning classification algorithms. We selected ten traditional machine learning classification methods to compare their performance with the GSNAc Model over the twenty datasets listed in Table 1 .

Machine learning classification algorithms usually fall into 3 categories, namely statistical, function-based and tree-based (hierarchical) models. We selected at least one algorithm from each category in order to present a balanced comparison.

The reported results, as summarized in Table 3 , show that GSNAc beats or on par with other classifiers on 10 of the datasets. Most notable success of these is on the PBC dataset 34 , where the problem is to predict one of 4 heavily imbalanced classes. On the remaining 10 other datasets, where GSNAc doesn’t score at top, we have noted comparable performance with other classifiers.

Detailed performance results of GSNAc in comparison with other classifiers are presented in Appendix I .

Explainability of the GSNAc model

Considering the rise of deep learners, ML models are increasingly getting complex in terms of their prediction model generation. The so-called black-box classifier models are not comprehendible for end-users on how the actual prediction is decided. For instance, a person may be interested in learning the reason for declining his/her loan application which was evaluated by an AI system.

Explainable AI (XAI) is a recent trend in machine learning research 2 , 35 which aims to identify how predictions are made in an explainable manner (see Fig.  7 ). Explainability and/ or interpretability is essential for end-users to effectively trust, and manage artificial intelligence applications 36 .

Explainable AI approach versus todays’ classifier models in a nutshell.

There are various (recent) research efforts conducted to address the explainability of the already existing machine learning classifier models. In 37 , researchers efficiently extended the use of a convolutional neural network classifier by developing an explainability module. With this extra module, they displayed comprehensionable prediction results of microseismic wave-form signal data while keeping excellent classification performance. Similarly, in 38 , researchers put significant effort to translate deep neural networks-based prediction results over traffic analysis data into visually comprehensible map data; thus providing an explainable (learned) trajectory segmentation to the end user of the deep learner model. Though relevant, we argue that these efforts do not actually coincide with the work developed in this research since GSNAc’s procedures and predictions are already designed with explainability in mind, and hence need no further translation procedure for explainability purposes.

SNA concentrates on generating, and visualizing interactions and information flows among network actors. The power of social networks is stemming mostly due to their capacity in revealing and visualizing interactions in a connected structure. It is no doubt that one can comprehend data more efficiently in a visual way, and network graphs allow us to better understand how nodes are similar to each other, which nodes bear most information, and most importantly, how information flows within a network. By converting and visualizing tabular data, we can reveal and learn several aspects, such as: which samples can distribute information to the largest audience, who is connected to the most influential nodes, and who creates fragility to graph, i.e., the single point of failure by being a single connector between two separate communities. As powered up by the idea of network graphs, GSNAc surely presents some advantages of social networks to its users as briefly summarized in the following three stages:

The first advantage is the visual classifier model (i.e., GCM) which makes sense of the data by keeping sample names as node names and keeping class information as a colored community. This is illustrated in Figs.  3 , 4 , and 5 .

The second advantage towards explainability lies in the actual visual prediction step (see Fig.  8 ): end-users can receive visual clues on how the test node is assigned into one class but not others by analyzing the structure of GCM nodes and weights of the edges.

The final advantage is based on the comparison of prediction results of GSNAc across different classifiers (see Fig.  9 ). GSNAc produces a set of graphs and displays the comparison on the overall prediction process. This way, an end-user can perceive how classifiers (in contrast to GSNAc) predicted a certain sample, whether true or false.

Sample visualization of the prediction step. Test node ADAR from the C. elegans dataset has been classified as CL-E (orange).

Overall classification result on C. Elegans dataset. Blue color implies that the specific sample has been predicted true by the respective classifier (such as AdaBoost); red color indicates false prediction. Boxes in black indicate cases where the same sample has been predicted true (as in blue colors) by XGBoost and AdaBoost classifiers, but false (as in red colors) by GSNAc, and boxes in orange indicate opposite cases (i.e., false by XGBoost and AdaBoost while true by GSNAc).

Discussion and further work

We have proposed GSNAc as a novel graph-based machine learning classifier which works on both numerical and categorical tabular datasets. It outperforms the previous version named SNAc both in performance and capability of handling a wide range of datasets. The main contribution of GSNAc is its capability of visualizing the decision-making process behind the model, while maintaining a fine prediction performance when compared to other classifiers.

GSNAc uses easy-to-grasp similarity-based metrics in graph generation and prediction steps; so might be a choice of some group of end-users who would like to diagrammatically perceive the whole classification process. Since GSNAc also provides prediction margins to end-user, one of its other advantages might be seen as determining and transferring low-margined classification decisions to a human expert for further investigation.

We demonstrated that GSNAc outperforms or is on par with state-of-the-art classifiers across different domains in terms of prediction performance. However, the main drawback of GSNAc is the duration of its run, since its core data structure is a ‘graph’ which has a processing complexity of O(n 2 ). Except for scalability, we are not aware of any shortcomings of this Model.

Lastly, we believe in the future this work can be effectively extended into node classification problems.

Data availability

The datasets used and/or analysed during the current study available from the corresponding author on reasonable request.

Abbreviations

Explainable artificial intelligence

Generalized social network analysis-based classifier

Graph classifier model

Social network

Social network analysis

Social network analysis-based classifier

Machine learning

Natural language processing

Chui, M. C. M. et al. Notes from the AI Frontier: Insights from Hundreds of Use Cases (McKinsey Global Institute, 2018).

Google Scholar  

Adadi, A. & Berrada, M. Peeking inside the black-box: A survey on explainable artificial intelligence (XAI). IEEE Access 6 , 52138–52160 (2018).

Article   Google Scholar  

Alhajj, R. & Rokne, J. (eds) Encyclopedia of Social Network Analysis and Mining (Springer New York, 2018).

Özyer, T., Ucer, S. & Iyidogan, T. Employing social network analysis for disease biomarker detection. Int. J. Data Min. Bioinforma. 12 (3), 343 (2015).

Üçer, S., Koçak, Y., Ozyer, T. & Alhajj, R. Social network Analysis-based classifier (SNAc): A case study on time course gene expression data. Comput. Methods Programs Biomed. 150 , 73–84 (2017).

Tabassum, S., Pereira, F. S. F., Fernandes, S. & Gama, J. Social network analysis: An overview. WIREs Data Min. Knowl. Discov. 8 (5), e1256 (2018).

Bishop, C. M. Pattern Recognition and Machine Learning (Springer, Preface p.viii, 2006).

MATH   Google Scholar  

Chen, T. & Guestrin, C. XGBoost: a scalable tree boosting system. In Proc. 22nd ACM SIGKDD Int. Conf. Knowl. Discov. Data Min. , 785–794 (2016).

Bansal, S. Data Science Trends on Kaggle !! (Kaggle, 2022).

LeCun, Y., Bengio, Y. & Hinton, G. Deep learning. Nature 521 (7553), 436–444 (2015).

Article   ADS   CAS   Google Scholar  

Kumar, R., Novak, J. & Tomkins, A. Structure and evolution of online social networks. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining—KDD ’06, Philadelphia, PA, USA, 611 (2006) (Accessed 26 Feb 2022).

Shanavas, N., Wang, H., Lin, Z. & Hawe, G. Knowledge-driven graph similarity for text classification. Int. J. Mach. Learn. Cybern. 12 (4), 1067–1081 (2021).

Zhu, X., Ghahramani, Z. & Lafferty, J. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning , 912–919, Washington, DC, USA (2003).

Belkin, M., Niyogi, P. & Sindhwani, V. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res. 7 , 2399–2434 (2006).

MathSciNet   MATH   Google Scholar  

Kipf, T. N. & Welling, M. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR) (2017).

Zhu, Y. et al. Converting tabular data into images for deep learning with convolutional neural networks. Sci. Rep. 11 (1), 11325 (2021).

Kuhn, M. & Johnson, K. Applied Predictive Modeling , 1st ed. 2013, Corr. 2nd printing 2018 edition. (Springer, 2013).

Kuhn, M. & Johnson, K. Feature Engineering and Selection: A Practical Approach for Predictive Models (CRC Press, Taylor & Francis Group, 2020).

Bhandari, A. Feature scaling|standardization vs normalization. Analytics Vidhya, (2020).

Deza, M. M. & Deza, E. Encyclopedia of Distances (Springer, 2016).

Book   Google Scholar  

Cook, S. J. et al. Whole-animal connectomes of both Caenorhabditis elegans sexes. Nature 571 (7763), 63–71 (2019).

Emmons, S. W. The beginning of connectomics: A commentary on White et al. (1986) ‘The structure of the nervous system of the nematode Caenorhabditis elegans ’. Philos. Trans. R. Soc. B Biol. Sci. 370 (1666), 20140309 (2015).

Badhwar, R. & Bagler, G. Control of neuronal network in Caenorhabditis elegans . PLoS ONE 10 (9), e0139204 (2015).

Varshney, L. R., Chen, B. L., Paniagua, E., Hall, D. H. & Chklovskii, D. B. Structural properties of the Caenorhabditis elegans neuronal network. PLoS Comput. Biol. 7 (2), e1001066 (2011).

The Insurance Company Benchmark (COIL 2000). http://kdd.ics.uci.edu/databases/tic/tic.data.html (Accessed 30 Dec 2021).

Alamsyah, A. et al. Community detection methods in social network analysis. Adv. Sci. Lett. 20 (1), 250–253 (2014).

Blondel, V. D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 2008 (10), P10008 (2008).

Clauset, A., Newman, M. E. J. & Moore, C. Finding community structure in very large networks. Phys. Rev. E 70 (6), 066111 (2004).

Article   ADS   Google Scholar  

Dianati, N. Unwinding the hairball graph: Pruning algorithms for weighted complex networks. Phys. Rev. E. 93 (1), 012304 (2016).

Article   ADS   MathSciNet   Google Scholar  

Edge, D., Larson, J., Mobius, M. & White, C. Trimming the hairball: Edge cutting strategies for making dense graphs usable. In 2018 IEEE International Conference on Big Data (Big Data) , (2018).

Han, J., Kamber, M. & Pei, J. Data Mining: Concepts and Techniques (2011).

“6.3. Preprocessing data,” scikit-learn. http://scikit-learn.org/stable/modules/preprocessing.html , (2021).

Pedregosa, F. et al. Scikit-learn: Machine learning in python. J. Mach. Learn. Res. 12 , 2825–2830 (2011).

Fleming, T. R. & Harrington, D. P. Counting processes and survival analysis. (Wiley-Interscience, 2005). (Accessed 13 Jan 2022).

Das, A. & Rad, P. Opportunities and Challenges in Explainable Artificial Intelligence (XAI): A Survey . ArXiv: 200611371 Cs (2020).

Gunning, D. et al. XAI—Explainable artificial intelligence. Sci. Robot. 4 , eaay7120 (2019).

Bi, X. et al. Explainable time–frequency convolutional neural network for microseismic waveform classification. Inf. Sci. 546 , 883–896. https://doi.org/10.1016/j.ins.2020.08.109 (2021).

Article   MathSciNet   MATH   Google Scholar  

Bi, X. et al. An uncertainty-based neural network for explainable trajectory segmentation. ACM Trans. Intell. Syst. Technol. 13 (1), 1–18. https://doi.org/10.1145/3467978 (2022).

Download references

Author information

Authors and affiliations.

The Scientific and Technological Research Council of Turkey, TUBITAK, Ankara, Turkey

Serkan Ucer

Department of Computer Engineering, Ankara Medipol University, Ankara, Turkey

Tansel Ozyer

Department of Computer Science, University of Calgary, Alberta, Canada

Reda Alhajj

Department of Computer Engineering, Istanbul Medipol University, Istanbul, Turkey

Department of Heath Informatics, University of Southern Denmark, Odense, Denmark

You can also search for this author in PubMed   Google Scholar

Contributions

All authors (S.U., T.O. and R.A.) developed the methodology, S.U. wrote the programs, run the experiments, analyzed the results and wrote the manuscript. All authors reviewed and approved the manuscript.

Corresponding author

Correspondence to Reda Alhajj .

Ethics declarations

Competing interests.

The authors declare no competing interests.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Supplementary information., rights and permissions.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Cite this article.

Ucer, S., Ozyer, T. & Alhajj, R. Explainable artificial intelligence through graph theory by generalized social network analysis-based classifier. Sci Rep 12 , 15210 (2022). https://doi.org/10.1038/s41598-022-19419-7

Download citation

Received : 13 March 2022

Accepted : 29 August 2022

Published : 08 September 2022

DOI : https://doi.org/10.1038/s41598-022-19419-7

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

By submitting a comment you agree to abide by our Terms and Community Guidelines . If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.

Quick links

• Explore articles by subject
• Guide to authors
• Editorial policies

Sign up for the Nature Briefing: AI and Robotics newsletter — what matters in AI and robotics research, free to your inbox weekly.

Help | Advanced Search

Computer Science > Data Structures and Algorithms

Title: graph theory and its uses in graph algorithms and beyond.

Abstract: Graphs are fundamental objects that find widespread applications across computer science and beyond. Graph Theory has yielded deep insights about structural properties of various families of graphs, which are leveraged in the design and analysis of algorithms for graph optimization problems and other computational optimization problems. These insights have also proved helpful in understanding the limits of efficient computation by providing constructions of hard problem instances. At the same time, algorithmic tools and techniques provide a fresh perspective on graph theoretic problems, often leading to novel discoveries. In this thesis, we exploit this symbiotic relationship between graph theory and algorithms for graph optimization problems and beyond. This thesis consists of three parts. In the first part, we study a graph routing problem called the Node-Disjoint Paths (NDP) problem. Given a graph and a set of source-destination pairs of its vertices, the goal is to route the maximum number of pairs via node-disjoint paths. We come close to resolving the approximability of NDP by showing that it is $n^{\Omega(1/poly\log\log n)}$-hard to approximate, even on grid graphs, where n is the number of vertices. In the second part of this thesis, we use graph decomposition techniques developed for efficient algorithms to derive a graph theoretic result. We show that for every n-vertex expander graph G, if H is any graph with at most $O(n/\log n)$ vertices and edges, then H is a minor of G. In the last part, we show that the graph theoretic tools and graph algorithmic techniques can shed light on problems seemingly unrelated to graphs. We show that the randomized space complexity of the Longest Increasing Subsequence (LIS) problem in the streaming model is intrinsically tied to the query-complexity of the Non-Crossing Matching problem on graphs in a new model of computation that we define.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Research Trends in Graph Theory and Applications

• © 2021
• Daniela Ferrero   ORCID: https://orcid.org/0000-0003-4675-1814 0 ,
• Leslie Hogben   ORCID: https://orcid.org/0000-0003-1673-3789 1 ,
• Sandra R. Kingan   ORCID: https://orcid.org/0000-0002-8232-5540 2 ,
• Gretchen L. Matthews   ORCID: https://orcid.org/0000-0002-8977-8171 3

Department of Mathematics, Texas State University, San Marcos, USA

You can also search for this editor in PubMed   Google Scholar

Department of Mathematics, Iowa State University, Ames, USA

Department of mathematics, brooklyn college and the graduate center, city university of new york, new york, usa, department of mathematics, virginia polytechnic institute and state university, blacksburg, usa.

• Features research in a broad variety of problems in different areas of graph theory
• Each chapter offers an introduction to a graph theory topic of current research, aiming at clarity and high-quality exposition while emphasizing recent advances and open problems
• Presents concepts and ideas thoroughly and with details
• Each chapter corresponds to research proposed and led by prominent research experts in each field

Part of the book series: Association for Women in Mathematics Series (AWMS, volume 25)

2823 Accesses

4 Citations

2 Altmetric

This is a preview of subscription content, log in via an institution to check access.

Access this book

• Available as EPUB and PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (6 chapters)

Front matter, finding long cycles in balanced tripartite graphs: a first step.

• Gabriela Araujo-Pardo, Zhanar Berikkyzy, Jill Faudree, Kirsten Hogenson, Rachel Kirsch, Linda Lesniak et al.

Product Thottling

• Sarah E. Anderson, Karen L. Collins, Daniela Ferrero, Leslie Hogben, Carolyn Mayer, Ann N. Trenk et al.

Analysis of Termatiko Sets in Measurement Matrices

• Katherine F. Benson, Jessalyn Bolkema, Kathryn Haymaker, Christine Kelley, Sandra R. Kingan, Gretchen L. Matthews et al.

The Threshold Dimension and Threshold Strong Dimension of a Graph: A Survey

• Nadia Benakli, Novi H. Bong, Shonda Dueck (Gosselin), Beth Novick, Ortrud R. Oellermann

Symmetry Parameters for Mycielskian Graphs

• Debra Boutin, Sally Cockburn, Lauren Keough, Sarah Loeb, K. E. Perry, Puck Rombach

Reconfiguration Graphs for Dominating Sets

• Kira Adaricheva, Chassidy Bozeman, Nancy E. Clarke, Ruth Haas, Margaret-Ellen Messinger, Karen Seyffarth et al.
• graph symmetries
• metric dimension
• graph searching
• data storage
• power domination

About this book

Editors and affiliations.

Daniela Ferrero

Leslie Hogben

Sandra R. Kingan

Gretchen L. Matthews

About the editors

Bibliographic information.

Book Title : Research Trends in Graph Theory and Applications

Editors : Daniela Ferrero, Leslie Hogben, Sandra R. Kingan, Gretchen L. Matthews

Series Title : Association for Women in Mathematics Series

DOI : https://doi.org/10.1007/978-3-030-77983-2

Publisher : Springer Cham

eBook Packages : Mathematics and Statistics , Mathematics and Statistics (R0)

Copyright Information : The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2021

Hardcover ISBN : 978-3-030-77982-5 Published: 07 September 2021

Softcover ISBN : 978-3-030-77985-6 Published: 08 September 2022

eBook ISBN : 978-3-030-77983-2 Published: 06 September 2021

Series ISSN : 2364-5733

Series E-ISSN : 2364-5741

Edition Number : 1

Number of Pages : XVIII, 135

Number of Illustrations : 47 b/w illustrations

Topics : Graph Theory , Computer Communication Networks

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Theory and Applications of Graphs

Home > Journals > TAG

Theory and Applications of Graphs (TAG) publishes high quality papers containing results of wide interest in the areas of graph theory and its applications.

As a platinum open access journal, TAG is freely available to both authors and readers.

Journal promotional flyer available here .

See the Aims and Scope for more information about the journal.

Additional Instructions for Screen Reader Users

The Readership Activity Map feature further down the page presents a real time interactive world map with pins indicating where documents from our collection have been downloaded recently. Begin reading after the Zoom buttons to find additional real time statistics.

Current Issue: Volume 11, Issue 1 (2024)

Recent studies on the super edge-magic deficiency of graphs Rikio Ichishima, Susana C. Lopez, Francesc Muntaner, and Yukio Takahashi

Strongly i-Bicritical Graphs Michelle Edwards, Gary MacGillivray, and Shahla Nasserasr

Approval Gap of Weighted k-Majority Tournaments Jeremy Coste, Breeann Flesch, Joshua D. Laison, Erin McNicholas, and Dane Miyata

• Journal Home
• About This Journal
• Aims & Scope
• Editorial Board
• Submit Article
• Most Popular Papers
• Receive Email Notices or RSS

Special Issues:

• Dynamic Surveys

Search GS Commons

Advanced Search

ISSN: 2470-9859

Home | About | FAQ | My Account | Accessibility Statement

Privacy Copyright

Information

• Author Services

Initiatives

You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader.

All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess .

Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications.

Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers.

Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.

Original Submission Date Received: .

• Active Journals
• Find a Journal
• Proceedings Series
• For Authors
• For Reviewers
• For Editors
• For Librarians
• For Publishers
• For Societies
• For Conference Organizers
• Open Access Policy
• Institutional Open Access Program
• Special Issues Guidelines
• Editorial Process
• Research and Publication Ethics
• Article Processing Charges
• Testimonials
• Preprints.org
• SciProfiles
• Encyclopedia

Journal Menu

• Mathematics Home
• Aims & Scope
• Editorial Board
• Reviewer Board
• Topical Advisory Panel
• Instructions for Authors
• Special Issues
• Sections & Collections
• Article Processing Charge
• Indexing & Archiving
• Editor’s Choice Articles
• Most Cited & Viewed
• Journal Statistics
• Journal History
• Journal Awards
• Society Collaborations
• Conferences
• Editorial Office

Journal Browser

• arrow_forward_ios Forthcoming issue arrow_forward_ios Current issue
• Vol. 12 (2024)
• Vol. 11 (2023)
• Vol. 10 (2022)
• Vol. 9 (2021)
• Vol. 8 (2020)
• Vol. 7 (2019)
• Vol. 6 (2018)
• Vol. 5 (2017)
• Vol. 4 (2016)
• Vol. 3 (2015)
• Vol. 2 (2014)
• Vol. 1 (2013)

Find support for a specific problem in the support section of our website.

Please let us know what you think of our products and services.

Visit our dedicated information section to learn more about MDPI.

Recent Advances in Chemical Graph Theory and Their Applications

Special issue editors, special issue information.

• Published Papers

A special issue of Mathematics (ISSN 2227-7390). This special issue belongs to the section " Network Science ".

Deadline for manuscript submissions: closed (31 January 2021) | Viewed by 21878

Share This Special Issue

Dear Colleagues,

Since the seminal paper of the American chemist Harold Wiener in 1947, many numerical quantities of graphs have been introduced and extensively studied in order to describe various physicochemical properties. Such graph invariants are most commonly referred to as topological indices and are often defined using degrees of vertices, distances between vertices, eigenvalues, symmetries, and many other properties of graphs. It is desirable for a topological index to also be a molecular descriptor. In order to establish the connection between topological indices and the properties or activities of studied compounds, quantitative structure–activity relationships (QSAR) and quantitative structure–property relationships (QSPR) must be performed. This enables the process of finding new compounds with desired properties in silico instead of in vitro.

There are well studied groups of molecules composed of carbon and hydrogen atoms, but modeling of more complex heteroatomic compounds is much more challenging. On the other hand, topological indices have also found enormous applications in rapidly growing research of complex networks, which include communications networks, social networks, biological networks, etc. In such networks, these indices are used as measures for various structural properties.

The purpose of this Special Issue is to report and review recent developments concerning mathematical properties, methods of calculations, and applications of topological indices in any area of interest. Moreover, papers on other topics in chemical graph theory are also welcome.

Prof. Dr. Petra Zigert Pletersek Dr. Niko Tratnik Guest Editors

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website . Once you are registered, click here to go to the submission form . Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Mathematics is an international peer-reviewed open access semimonthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 2600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

• Topological indices
• Molecular descriptors
• Methods of calculations
• QSP(A)R analysis
• Molecular graphs
• Complex molecules
• Nanostructures
• Different measures in networks

Published Papers (5 papers)

Graphical abstract

Further Information

Mdpi initiatives, follow mdpi.

Subscribe to receive issue release notifications and newsletters from MDPI journals

Breadcrumbs Section. Click here to navigate to respective pages.

Recent Advancements in Graph Theory

DOI link for Recent Advancements in Graph Theory

Get Citation

Graph Theory is a branch of discrete mathematics. It has many applications to many different areas of Science and Engineering. This book provides the most up-to-date research findings and applications in Graph Theory.

This book focuses on the latest research in Graph Theory. It provides recent findings that are occurring in the field, offers insights on an international and transnational levels, identifies the gaps in the results, and includes forthcoming international studies and research, along with its applications in Networking, Computer Science, Chemistry, and Biological Sciences, etc.

The book is written with researchers and post graduate students in mind.

TABLE OF CONTENTS

Chapter 1 | 8  pages, graceful labeling for eight sprocket graph, chapter 2 | 10  pages, universal absolute mean graceful graphs, chapter 3 | 6  pages, universal α-graceful gear related graphs, chapter 4 | 9  pages, l(2, 1) - labeling on jahangir graph, chapter 5 | 11  pages, v 4 - cordial labeling of some ladder and book related graphs, chapter 6 | 9  pages, sd-prime cordial labeling of double k-polygonal snake graph, chapter 7 | 17  pages, edge product cordial and total edge product cordial labeling of some wheel related graphs, chapter 8 | 8  pages, product cordial labeling for the line graph of bistar, chapter 9 | 16  pages, sum divisor cordial labeling for vertex switching of cycle related graphs, chapter 10 | 15  pages, a few results on fibonacci cordial labeling, chapter 11 | 17  pages, some more parity combination cordial graphs, chapter 12 | 13  pages, total neighborhood prime labeling of join graphs, chapter 13 | 15  pages, gaussian vertex prime labeling of some graphs obtained from origami models, chapter 14 | 10  pages, vertex magic total labeling of tensor product of cycles, chapter 15 | 8  pages, antimagic labeling of some star and bistar related graphs, chapter 16 | 11  pages, distance magic and distance antimagic labeling of some product graphs, chapter 17 | 13  pages, graphs from subgraphs, chapter 18 | 13  pages, unit graphs having their domination number half their order, chapter 19 | 11  pages, the pendant number of some graph products, chapter 20 | 13  pages, wiener index of tensor product of cycle graph and some other graphs, chapter 21 | 14  pages, wiener index of some zero-divisor graphs, chapter 22 | 11  pages, algebraic signed graphs: a review, chapter 23 | 6  pages, nullity and energy of complete tripartite graphs, chapter 24 | 10  pages, some new results on restrained edge domination number of graphs, chapter 25 | 26  pages, some new graph coloring problems, chapter 26 | 13  pages, total global dominator coloring of graphs, chapter 27 | 10  pages, rainbow vertex connection number of a class of triangular snake graph, chapter 28 | 14  pages, hamiltonian chromatic number of trees, chapter 29 | 7  pages, some results on degree sum energy of a graph, chapter 30 | 20  pages, randić energy of some graphs, chapter 31 | 10  pages, l-spectra of graphs obtained by duplicating graphs elements.

• Privacy Policy
• Terms & Conditions
• Cookie Policy
• Taylor & Francis Online
• Taylor & Francis Group
• Students/Researchers
• Librarians/Institutions

Connect with us

Registered in England & Wales No. 3099067 5 Howick Place | London | SW1P 1WG © 2024 Informa UK Limited

List of Publications

Pre-prints -- subject to revision.

• Random 2-SAT with prescribed literal degrees Algorithmica 48, 249-265 [Co-authors: C. Cooper and G. Sorkin]
• The cover time of sparse random graphs Random Structures and Algorithms 30, John Wiley and Sons, 1-16. [Co-author: C.Cooper]
• Random k-SAT: A tight threshold for moderately growing k Combinatorica 25, 297-305. [Co-author: N.C. Wormald]
• Fast Monte-Carlo algorithms for finding low rank approximations JACM 51, 1025-1041 [Co-authors: R.Kannan and S.Vempala]
• Avoidance of a giant component in half the edge set of a random graph Program to check some calculations Random Structures and Algorithms 25, John Wiley and Sons, 432-449. [Co-authors: T. Bohman and N. Wormald]
• The size of the largest strongly connected component of a random digraph with a given degree sequence Combinatorics, Probability and Computing 13, 319-338. [Co-author: C.Cooper]
• On the b-independence number of sparse random graphs Combinatorics, Probability and Computing 13, 295-310. [Co-author: G. Atkinson]
• The emergence of a giant component in a random subgraph of pseudo-random graphs Random Structures and Algorithms 24, John Wiley and Sons, 42-50. [Co-authors: M.Krivelevich, R. Martin]
• Randomly colouring graphs with lower bounds on girth and maximum degree Random Structures and Algorithms 23, John Wiley and Sons, 167-179. [Co-author: M.E. Dyer]
• Crawling on web graphs Internet Mathematics 1, 57-90 [Co-author: C.Cooper]
• On Randomly Generated Intersecting Hypergraphs Electronic Journal on Combinatorics, R29 [Co-authors: T. Bohman, C.Cooper, R. Martin, M. Ruszinko]
• Arc-Disjoint Paths in Expander Digraphs SIAM Journal on Computing 32, 326-344. [Co-author: T. Bohman]
• On a general model of web graphs Random Structures and Algorithms 22, John Wiley and Sons, 311-335. [Co-author: C. Cooper]
• A probabilistic analysis of randomly generated binary constraint satisfaction problems Theoretical Computer Science 290, 1815-1828 [Co-authors: M.E. Dyer and M. Molloy]
• The cover time of sparse random graphs JOURNAL VERSION Proceedings of SODA 2003, 140-147. [Co-author: C.Cooper]
• How many random edges make a dense graph Hamiltonian? Random Structures and Algorithms 22, 33-42. [Co-authors: T. Bohman, R. Martin]
• Hamilton Cycles in Random Subgraphs of Pseudo-Random Graphs Discrete Mathematics 256, 137-150 [Co-author: M. Krivelevich]
• On graph irregularity strength Journal of Graph Theory 41, 120-137. [Co-authors: R.J. Gould, M. Karonski, F. Pfender]
• Random regular graphs of non-constant degree: independence and chromatic number Combinatorics, Probability and Computing 11, 323-342. [Co-authors: C.Cooper, B.Reed, O.Riordan]
• On random symmetric travelling salesman problems Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 789-790. JOURNAL VERSION
• Random regular graphs of non-constant degree: connectivity and Hamilton cycles Combinatorics, Probability and Computing 11, 249-262. [Co-authors: C.Cooper, B.Reed]
• Probabilistic analysis of the Traveling Salesman Problem The traveling salesman problem and its variations, G. Gutin and A.P. Punnen (Eds.), Kluwer Academic Publisher, 257-308. [Co-author: J.Yukich]
• Crawling on web graphs STOC 2002, 419-427 JOURNAL VERSION [Co-author: C.Cooper]
• Random k-SAT: A tight threshold for moderately growing k Proceedings of the Fifth International Symposium on Theory and Applications of Satisfiability Testing, 1-6. JOURNAL VERSION [Co-author: N.C. Wormald]
• Optimal sequencing by hybridization in rounds Journal of Computational Biology 9, 355-369. [Co-author: B. Halldorsson]
• A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems Mathematical Programming A 92, 1-36. [Co-authors: S.Arora and H.Kaplan]
• Multi-coloured Hamilton cycles in randomly coloured random graphs Combinatorics, Probability and Computing 11, 129--134. [Co-author: C. Cooper]
• A note on random 2-SAT with prescribed literal degrees Proceedings of SODA 2002, 316-320. JOURNAL VERSION [Co-authors: C. Cooper and G. Sorkin]
• Balls and Bins Models with Feedback Proceedings of SODA 2002, 308-315. [Co-authors: E. Drinea and M. Mitzenmacher]
• Vertex covers by edge disjoint cliques Combinatorica 21 171-197. [Co-authors: T.Bohman, M.Ruszinko, L.Thoma]
• G-intersecting families Combinatorics, Probability and Computing 10, 367-384. [Co-authors: T.Bohman, M.Ruszinko, L.Thoma]
• Arc-Disjoint Paths in Expander Digraphs Proceedings of FOCS 2001, 558-567. [Co-author: T. Bohman] JOURNAL VERSION
• On a general model of web graphs Proceedings of ESA 2001, 500-511. [Co-author: C. Cooper] JOURNAL VERSION
• Randomly colouring graphs with lower bounds on girth and maximum degree Proceedings of FOCS 2001, 579-587. JOURNAL VERSION [Co-author: M.E. Dyer]
• Avoiding a giant component Random Structures and Algorithms 19, John Wiley and Sons, 75-85 [Co-author: T. Bohman]
• Optimal sequencing by hybridization in rounds Proceedings of RECOMB2001, 141-148. [Co-author: B. Halldorsson] JOURNAL VERSION
• Edge disjoint paths in expander graphs SIAM Journal on Computing 30, 1790-1801.
• On Markov chains for randomly H-colouring a graph Journal of Algorithms 39, 117-134 [Co-authors: C.Cooper and M.E.Dyer]
• Hamilton cycles in the union of random permutations Random Structures and Algorithms 18, John Wiley and Sons, 83-94.
• The probabilistic relationship between the assignment and asymmetric traveling salesman problems Proceedings of SODA 2001, 652-660. [Co-author: G. Sorkin] JOURNAL VERSION
• On the number of perfect matchings and Hamilton cycles in epsilon-regular non-bipartite graphs Electronic Journal of Combinatorics 7, R57.
• Mixing properties of the Swendsen-Wang process on classes of graphs II Journal of Mathematical Physics 4, 1499-1527. [Co-authors: C.Cooper, M.E.Dyer and R.Rue]
• A note on random minimum length spanning trees Electronic Journal of Combinatorics 7, R41. [Co-authors: M.Ruszinko, L.Thoma]
• Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs Combinatorics, Probability and Computing 9, 241-264. [Co-author: L.Zhao]
• Hamilton cycles in random graphs and directed graphs Random Structures and Algorithms 16, John Wiley and Sons, 369-401. [Co-author: C.Cooper]
• Edge disjoint paths in expander graphs Proceedings of SODA 2000, 717-725. JOURNAL VERSION
• Average-case analysis of shortest-paths algorithms in the vertex potential model Random Structures and Algorithms 16, John Wiley and Sons, 33-46. [Co-authors: C.Cooper, V.Priebe and K.Mehlhorn]
• A Note on Sparse Random Graphs and Cover Graphs Electronic Journal of Combinatorics 7, R19. [Co-authors: T.Bohman, M.Ruszinko, L.Thoma]
• On Hamilton cycles in sparse random graphs with minimum degree at least k Journal of Graph Theory 34, John Wiley and Sons, 42-59. [Co-authors: B.Bollobas, C.Cooper and T.I.Fenner]
• Min-Wise independent linear permutations Electronic Journal of Combinatorics 7, R26. [Co-authors: T.Bohman and C.Cooper]
• On counting independent sets in sparse graphs Proceedings of FOCS '99, 210-217. [Co-authors: M.E.Dyer and M.R.Jerrum] JOURNAL VERSION
• On the Power of Universal Bases in Sequencing by Hybridization Proceedings of RECOMB '99 Journal version appeared as Optimal Reconstruction of a Sequence from its Probes in Journal of Computational Biology 6, 361-368. [Co-authors: F.Preparata and E.Upfal]
• Mixing Properties of the Swendsen-Wang Process on Classes of Graphs Random Structures and Algorithms 15, John Wiley and Sons, 242-261. [Co-author: C.Cooper]
• Splitting an expander graph Journal of Algorithms 33, 166-172. [Co-author: M.Molloy]
• Existence and construction of edge low congestion paths on expander graphs Random Structures and Algorithms 14, John Wiley and Sons, 87-109. [Co-authors: A.Broder and E.Upfal]
• Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs Proceedings of SODA '99, 346-355. JOURNAL VERSION [Co-author: L.Zhao]
• Torpid mixing of some MCMC algorithms in Statistical Physics Proceedings of FOCS '99, 218-229. [Co-authors: C.Borgs, J.Chayes, J.H.Kim, P.Tetali, E.Vigoda and V.Vu]
• Clustering in large graphs and matrices Proceedings of SODA '99, 291-299 [Co-authors: P.Drineas, R.Kannan, S.Vempala and V.Vinay] JOURNAL VERSION
• A simple algorithm for constructing Szemeredi's Regularity Partition Electronic Journal of Combinatorics, 6(1) R17. [Co-author: R.Kannan]
• Optimal construction of edge-disjoint paths in random graphs SIAM Journal on Computing 28, 541-574. [Co-authors: A.Z.Broder, S.Suen and E.Upfal]
• On Perfect Matchings and Hamiltonian Cycles in Sums of Random Trees SIAM Journal on Discrete Mathematics 12, 208-216. [Co-authors: M.Karonski and L.Thoma]
• Log-Sobolev inequalities and sampling from log-concave distributions Annals of Applied Probability 9, 14-26. [Co-author: R. Kannan]
• Quick approximation to matrices and applications Combinatorica 19, 175-220.  [Co-author: R. Kannan]
• Maximum matchings in sparse random graphs: Karp-Sipser revisited Random Structures and Algorithms 12, John Wiley and Sons ,111-178. [Co-authors: J.Aronson and B.Pittel]
• Greedy algorithms for the shortest common superstring that are asymptotically optimal Algorithmica 21, 21-36. [Co-author: W.Szpankowski]
• Min-Wise Independent permutations Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 327-336. [Co-authors: A.Broder, M.Charikar, M.Mitzenmacher]
• Approximately counting Hamilton cycles in dense graphs SIAM Journal on Computing 27, 1262-1272. [Co-authors: M.E.Dyer and M.R.Jerrum]
• On balls and bins with deletions Proceedings of Random '98, Lecture Notes in Computer Science 1518, Springer, 145-158. [Co-authors: M.Cole, B.Maggs, M.Mitzenmacher, A.Richa, R.Sitaraman]
• Disjoint Paths in Expander Graphs via Random Walks: a Short Survey Proceedings of Random '98, Lecture Notes in Computer Science 1518, Springer, 1-14.
• A polynomial-time algorithm for learning noisy linear threshold functions Algorithmica 22, 35-52. [Co-authors: A.Blum, R.Kannan and S.Vempala]
• Average case analysis of the merging algorithm of Hwang and Lin Algorithmica 22, 483-489. [Co-authors: W.Fernandez de la Vega and M.Santha]
• Fast Monte-Carlo algorithms for finding low rank approximations JOURNAL VERSION Proceedings of 1998 IEEE Symposium on Foundations of Computer Science, 370-378. [Co-authors: R.Kannan and S.Vempala]
• Random minimum length spanning trees in regular graphs Combinatorica 18, 311-333. [Co-author: A.Beveridge and C.McDiarmid]
• Existence and construction of edge low congestion paths on expander graphs Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 531-539. [Co-authors: A.Broder and E.Upfal] JOURNAL VERSION
• Average-case analysis of shortest-paths algorithms in the vertex potential model. Randomization and approximation techniques in Computer Science (Proceedings of RANDOM '97) Lecture Notes in Computer Science 1269, 15-26. [Co-authors: C.Cooper, V.Priebe and K.Mehlhorn] JOURNAL VERSION
• Improved approximation algorithms for MAX k-CUT and MAX BISECTION Algorithmica 18, 61-77. [Co-author: M.R.Jerrum]
• On the connectivity of random k-th nearest neighbour graphs Combinatorics, Probability and Computing 4, 343-362. [Co-author: C.Cooper]
• Analysis of Two Simple Heuristics on a Random Instance of k-SAT Journal of Algorithms 20, 312-355. [Co-author: S.Suen]
• Perfect matchings in random r-regular, s-uniform hypergraphs Combinatorics, Probability and Computing 5, 1-15. [Co-authors: C.Cooper, M.Molloy and B.Reed]
• Greedy algorithms for the shortest common superstring that are asymptotically optimal Proceedings of ESA96, Springer Lecture Notes in Computer Science 1136, 194-207. [Co-author: W.Szpankowski] JOURNAL VERSION
• Analysis of Parallel Algorithms for Finding A Maximal Independent Set in A Random Hypergraph Random Structures and Algorithms 9, John Wiley and Sons , 359-378. [Co-author: H.Chen]
• Generating and counting Hamilton cycles in random regular graphs Journal of Algorithms 21, 176-198. [Co-authors: M.R.Jerrum, M.Molloy, R.Robinson and N.C.Wormald]
• A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 21-30 [Co-authors: S.Arora and H.Kaplan] JOURNAL VERSION The journal version of this paper is in preparation.
• A polynomial-time algorithm for learning noisy linear threshold functions Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 330-338. [Co-authors: A.Blum, R.Kannan and S.Vempala] JOURNAL VERSION
• Learning linear transformations Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 359-368. [Co-authors: R.Kannan and M.R.Jerrum]
• The regularity lemma and approximation schemes for dense problems Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 12-20. [Co-author: R.Kannan] JOURNAL VERSION
• A general approach to dynamic packet routing with bounded buffers Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 390-399. [Co-authors: A.Z.Broder and E.Upfal] JOURNAL VERSION
• Coloring Bipartite Hypergraphs IPCO '96, 345-358. [Co-author: H.Chen]
• An efficient algorithm for the vertex-disjoint paths problem in random graphs. Proceedings of SODA '96, 261-268. [Co-authors: A.Z.Broder, S.Suen and E.Upfal]
• On the best case of heapsort Journal of Algorithms 20, 205-217. [Co-authors: B.Bollobas and T.I.Fenner]
• An Analysis of a Monte Carlo Algorithm for Estimating the Permanent Combinatorica 15, 67-83. [Co-author: M.R.Jerrum]
• Multicoloured Hamilton Cycles Electronic Journal of Combinatorics 2, R10 [Co-authors: M.Albert and B.Reed]
• Ordering Clone Libraries in Computational Biology Journal of Computational Biology 2, 207--218 [Co-authors: M.E.Dyer and S.Suen]
• When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem ? SIAM Journal on Computing 24, 484-493. [Co-authors: R.M.Karp and B.Reed]
• Polynomial Time Randomised Approximation Schemes for Tutte-Grothendieck Invariants: The Dense Case Random Structures and Algorithms 6, John Wiley and Sons , 459-478. [Co-authors: N.Alon and D.Welsh]
• Analysis of a simple greedy matching algorithm on random cubic graphs Combinatorics, Probability and Computing 4, 47-66. [Co-authors: A.J.Radcliffe and S.Suen]
• Perfect Matchings in Random s-Uniform Hypergraphs Random Structures and Algorithms 7, John Wiley and Sons , 41-57. [Co-author: S.Janson]
• Covering the edges of a random graph by cliques Combinatorica 15, 1-9. [Co-author: B.Reed]
• Multicoloured Hamilton cycles in random graphs: an anti-Ramsey threshold. Electronic Journal of Combinatorics 2, R19. [Co-author: C.Cooper]
• On key storage in secure networks Journal of Cryptology 8, 189-200. [Co-authors: M.E.Dyer, T.I.Fenner and A.Thomason]
• The worst-case running time of the random simplex algorithm is exponential in the height Information Processing Letters 56, 79-81. [Co-authors: A.Z.Broder, M.E.Dyer, P.Raghavan and E.Upfal]
• Improved approximation algorithms for MAX k-CUT and MAX BISECTION Proceedings of the fourth Integer Programming and Combinatorial Optimization Conference (IPCO4)}, Springer-Verlag Lecture Notes in Computer Science 920, 1-13. [Co-author: M.R.Jerrum] JOURNAL VERSION
• Probabilistic analysis of an algorithm in the theory of markets in indivisible goods Annals of Applied Probability 5, 768-808. [Co-author: B.Pittel]
• Random walks, totally unimodular matrices and a randomised dual simplex algorithm. Mathematical Programming 64, 1-16. [Co-author: M.E.Dyer]
• Multicoloured trees in random graphs Random Structures and Algorithms 5, John Wiley and Sons , 45-56. [Co-author: B.D.Mckay]
• Randomised greedy matching II Proceedings of 4th Annual Symposium on Discrete Algorithms (1994) 141-149. [Co-authors: J.Aronson, M.E.Dyer and S.Suen] JOURNAL VERSION
• Optimal construction of edge disjoint paths in random graphs Proceedings of 4th Annual Symposium on Discrete Algorithms (1994) 603-612 [Co-authors: A.Z.Broder, S.Suen and E.Upfal] JOURNAL VERSION
• Approximately counting Hamilton cycles in dense graphs Proceedings of 4th Annual ACM/SIAM Symposium on Discrete Algorithms 336-343 [Co-authors: M.E.Dyer and M.R.Jerrum] JOURNAL VERSION
• On the Problem of Approximating the Number of Bases of a Matroid Information Processing letters 50, 9-11. [Co-authors: Y.Azar and A.Broder]
• The probability of unique solutions of sequencing by hybridization Journal of Computational Biology 1, 105-110. [Co-authors: M.E.Dyer and S.Suen]
• Hamilton cycles in random regular digraphs Combinatorics, Probability and Computing 3, 39-50. [Co-authors: C.Cooper and M.J.Molloy]
• Finding hidden Hamilton cycles Random Structures and Algorithms 5, John Wiley and Sons , 395-410. [Co-authors: A.Broder and E.Shamir]
• Near-perfect token distribution Random Structures and Algorithms 5, John Wiley and Sons , 559-572 [Co-authors: A.Broder, E.Shamir and E.Upfal]
• Broadcasting in random graphs, Discrete Applied Mathematics 54, 77-79. [Co-author: M.Molloy]
• Hamilton cycles in a class of random directed graphs Journal of Combinatorial Theory B 62, 151-163 [Co-author: C.Cooper]
• Polynomial time randomised approximation schemes for the Tutte polynomial of dense graphs. Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science 24-35. [Co-authors: N.Alon and D.Welsh] JOURNAL VERSION
• On the complexity of computing the diameter of a polyhedron Journal of Computational Complexity 4, 207-219. [Co-author: S.Teng]
• Existence and construction of edge disjoint paths on expander graphs SIAM Journal of Computing 23, 976-989. [Co-authors: A.Broder and E.Upfal]
• On the satisfiability and maximum satisfiability of random 3-CNF formulas Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 322-330. [Co-authors: A.Broder and E.Upfal]
• Analysis of a simple greedy matching algorithm on random cubic graphs Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 341-351. [Co-authors: A.J.Radcliffe and S.Suen] JOURNAL VERSION
• The average performance of the greedy matching algorithm Annals of Applied Probability 3, 526-552. [Co-authors: M.E.Dyer and B.Pittel]
• Polychromatic Hamilton cycles Discrete Mathematics118, 69-74. [Co-author: B.Reed]
• A mildly exponential algorithm for estimating the number of knapsack solutions. Combinatorics, Probability and Computing 2, 271-284. [Co-authors: M.E.Dyer,R.Kannan, A. Kapoor, L.Perkovic and U.Vazirani]
• On the independence and chromatic numbers of random regular graphs Journal of Combinatorial Theory 54 , 123-132. [Co-author: T.Luczak]
• On the expected performance of a parallel algorithm for finding maximal independent sets Random Structures and Algorithms 3, John Wiley and Sons , 215 - 222. [Co-authors: N.Calkin and L.Kucera]
• On small subgraphs of random graphs Proceedings of Random Graphs 1989, Poznan, John Wiley and Sons 67 - 90.
• Counting Hamilton cycles in random directed graphs Random Structures and Algorithms 3, John Wiley and Sons , 235-242. [Co-author: S.Suen]
• Probabilistic analysis of the generalised assignment problem Mathematical Programming 55, 169-181. [Co-author: M.E.Dyer]
• Random walks, totally unimodular matrices and a randomised dual simplex algorithm. Proceedings of IPCO '92, 72-84. [Co-author: M.E.Dyer] JOURNAL VERSION
• When is the assignment bound asymptotically tight for the asymmetric traveling-salesman problem? Proceedings of IPCO '92, 453-461. [Co-author: R.M.Karp and B.Reed] JOURNAL VERSION
• Existence and construction of edge disjoint paths on expander graphs Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 140-149. [Co-authors: A.Broder and E.Upfal] JOURNAL VERSION
• On subgraph sizes in random graphs Combinatorics, Probability and Computing 1 , 123-134. [Co-authors: N.J.Calkin and B.D.Mckay]
• Separator based parallel divide and conquer in computational geometry Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architecture [Co-authors: G.L.Miller and S.Teng]
• Randomised greedy matching Random Structures and Algorithms 2, John Wiley and Sons , 29-46. [Co-author: M.E.Dyer]
• Occupancy problems and random algebras Discrete Mathematics 87 , 1-8. [Co-author: M.Albert]
• A random polynomial time algorithm for approximating the volume of convex bodies Journal of the Association for Computing Machinery 38 , 1-17. [Co-authors: M.E.Dyer and R.Kannan]
• Spanning maximal planar subgraphs of random graphs Random Structures and Algorithms 2, John Wiley and Sons , 225-232. [Co-author: B.Bollobas]
• A parallel algorithm for finding the lexicographically first depth first search tree in a random graph Random Structures and Algorithms 2, John Wiley and Sons , 233-240. [Co-author: M.E.Dyer]
• On the length of the longest monotone subsequence of a random permutation The Annals of Applied Probability 1 , 301-305.
• On hidden Hamilton cycles Proceedings of the 23rd Annual ACM Symposium on Theory of Computing,182-189. [Co-authors: A.Broder and E.Shamir] JOURNAL VERSION
• Computing the volume of a convex body: a case where randomness provably helps Proceedings of AMS Symposium on Probabilistic Combinatorics and Its Applications , 123-170. [Co-author: M.E.Dyer]
• On a conjecture of Bondy and Fan Ars Combinatoria 11, 191-205. [Co-authors: C.J.H.McDiarmid and B.Reed]
• Edge disjoint trees in random graphs Periodica Mathematica Hungarica 21 , 28-30 [Co-author: T.Luczak]
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets Random Structures and Algorithms 1, John Wiley and Sons , 39-50. [Co-author: N.Calkin]
• The limiting probability that a-in, b-out is strongly connected Journal of Combinatorial Theory 48 , 117-134. [Co-author: C. Cooper]
• On an optimisation problem with nested constraints Discrete Applied Mathematics 26 , 159-173. [Co-author: M.E. Dyer]
• Probabilistic analysis of graph algorithms Computing Supplement 7, Computational Graph Theory, Edited by Tinhofer, Mayr, Noltemeier and Syslo, Springer-Verlag , 209-234.
• Probabilistic analysis of the generalised assignment problem Proceedings of Integer Programming and Combinatorial Optimization 1, 189 - 200. [Co-author: M.E.Dyer] JOURNAL VERSION
• On the independence number of random graphs Discrete Mathematics 81 , 171-176.
• On patching algorithms for random asymmetric travelling salesman problems Mathematical Programming 46 , 361-378. [Co-author: M.E. Dyer]
• Pancyclic random graphs in Proceedings of Random Graphs '87, Edited by M.Karonski, J.Jaworski and A.Rucinski, John Wiley and Sons , 29-39. [Co-author: C. Cooper]
• Parallel colouring of random graphs in Proceedings of Random Graphs '87, Edited by M.Karonski, J.Jaworski and A.Rucinski, John Wiley and Sons , 41-52. [Co-author: L. Kucera]
• Hamiltonian cycles in a class of random graphs: one step further in Proceedings of Random Graphs '87, Edited by M.Karonski, J.Jaworski and A.Rucinski, John Wiley and Sons , 53-59. [Co-author: T. Luczak]
• Greedy matching on the line SIAM Journal on Computing 19 , 666-672. [Co-authors: C.J.H.McDiarmid and B.Reed]
• Hamilton cycles in random graphs with minimal degree at least k in A tribute to Paul Erdos, edited by A.Baker, B.Bollobas and A.Hajnal, 59 - 96. [Co-authors: B.Bollobas and T.I.Fenner]
• A new integer programming formulation of the permutation flowshop problem European Journal of Operations Research 40 , 90-98 [Co-author: J. Yadegar]
• Probabilistic analysis of random m-dimensional knapsack problems Mathematics of Operations Research 14 , 162-176. [Co-author: M.E. Dyer]
• A randomized algorithm for fixed dimensional linear programming Mathematical Programming 44 , 203-212. [Co-author: M.E. Dyer]
• Algorithms for assignment problems on an array processor Parallel Computing 11 , 151-162 [Co-authors: J.Yadegar, D.Parkinson and S.El-Horbaty]
• Algorithms for shortest paths problems on an array processor Proceedings of the Fourth International Conference on Supercomputing, Santa Clara CA. [Co-authors: J.Yadegar, D.Parkinson and S.El-Horbaty]
• Random graph orders Order 6 , 19-30. [Co-author: M.Albert]
• The solution of some random NP-hard problems in polynomial expected time Journal of Algorithms 10 , 451-489. [Co-author: M.E. Dyer]
• Survival time of a random graph Combinatorica 9 , 133-143.
• On the number of hamilton cycles in a random graph Journal of Graph Theory 13 , 719-735. [Co-author: C.Cooper]
• On matchings and Hamilton cycles in random graphs Surveys in Combinatorics, 1989, Proceedings of British Combinatorial Conference, 84-114.
• On random minimum length spanning trees Combinatorica 9 , 363-374. [Co-author: C.McDiarmid]
• A random polynomial time algorithm for approximating the volume of convex bodies Proceedings of 21st ACM Symposium on Theory of Computing, 375-381. [Co-authors: M.E.Dyer and R.Kannan] JOURNAL VERSION
• Probabilistic analysis of a relaxation for the k-median problem Mathematics of Operations Research 13, 1-31. [Co-authors: S. Ahn, C. Cooper and G. Cornuejols]
• On the random construction of heaps Information Processing Letters 27, 103-109.
• Reconstructing truncated integer variables satsifying linear congruences SIAM Journal on Computing 17, 262-280. [Co-authors: J. Hastad, R. Kannan, J.C. Lagarias, A. Shamir]
• Finding hamilton cycles in sparse random graphs Journal of Combinatorial Theory B 44, 230-250.
• An algorithm for finding hamilton cycles in random digraphs Journal of Algorithms 9 181-204.
• Partitioning random graphs into large cycles Discrete Mathematics 70 149-158.
• On the complexity of computing the volume of a polyhedron SIAM Journal on Computing 17 , 967-974. [Co-author: M.E. Dyer]
• Edge-colouring random graphs Journal of Combinatorial Theory B 45 , 135-149. [Co-authors: B. Jackson, C. Mc.Diarmid and B. Reed]
• On large induced trees in sparse random graphs Journal of Cominatorial Theory B42, 181-195. [Co-author: B. Jackson]
• Parallel algorithms for finding hamilton cycles in random graphs Information Processing Letters 25, 111-117.
• On the strength of connectivity of random subgraphs of the n-cube Annals of Discrete Mathematics, 33, 17-40. [Co-authors: M.E. Dyer and L.R. Foulds]
• A probabilistic analysis of the next fit decreasing bin packing heuristic Operations Research Letters 5, 233-236. [Co-authors: J. Csirik, J.B.G. Frenk, G. Galambos and A.H.G. Rinnooy Kan]
• On the exact solution of random travelling salesman problems with medium-sized integer costs SIAM Journal on Computing, 16, 1052-1072.
• Large holes in sparse random graphs Combinatorica 7, 265-274. [Co-author: B. Jackson]
• An algorithm for finding hamilton paths and cycles in random graphs Combinatorica 7, 327-341. [Co-authors: B.Bollobas and T.I.Fenner]
• On large matchings and cycles in sparse random graphs Discrete Mathematics 59, 243-256.
• On the Lagarias-Odlyzko algorithm for the subset-sum problem SIAM Journal on Computing 15, 536-539.
• Maximum matchings in a class of random graphs Journal of Combinatorial Theory Series B 40, 196-212.
• Planar 3DM is NP-Complete Journal of Algorithms 7, 174-184. [Co-author: M.E. Dyer]
• Linear programs with random costs Mathematical Programming 35, 3-16. [Co-authors: M.E. Dyer and C.J.H. Mc.Diarmid]
• Fast algorithms for some random NP-hard problems Extended abstract in the proceedings of the 27th Annual IEEE Symposium on the Foundations of Computer Science. [Co-author: M.E. Dyer]
• Expected behaviour of line balancing heuristics I.M.A. Journal on Mathematics in Management 1, 1-11. [Co-author: I. Baybars]
• On the value of a random minimum spanning tree problem Discrete Applied Mathematics 10, 47-56.
• An algorithm for finding hamiltonian cycles in random graphs Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 430-439. [Co-authors: B. Bollobas and T.I. Fenner] JOURNAL VERSION
• The shortest path problem for graphs with random arc-lengths Discrete Applied Mathematics 10, 57-77. [Co-author: G.R. Grimmett]
• On the complexity of partitioning graphs into connected subgraphs Discrete Applied Mathematics 10, 139-153. [Co-author: M.E. Dyer]
• An analysis of some graph theoretic heuristics for the facilities layout problem European Journal of Operational Research 20, 102-114. [Co-authors: M.E. Dyer and L.R. Foulds]
• A parallel algorithm for all-pairs shortest paths in a random graph Proceedings of the 22nd Allerton Conference on Communication, Control and Computing, 663-670. [Co-author: L. Rudolph]
• A simple heuristic for the p-centre problem Operations Research Letters 3, 285-288. [Co-author: M.E. Dyer]
• An algorithm for finding a matroid basis that maximises the product of the weights of the elements BIT 25, 434-438. [Co-author: T.I. Fenner]
• On matchings and hamiltonian cycles in random graphs Annals of Discrete Mathematics 28, 23-46. [Co-author: B. Bollobas]
• Limit distribution for the existence of hamiltonian cycles in random bipartite graphs European Journal of Combinatorics 6, 327-334.
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analysis European Journal of Operations Research 15, 100-109. [Co-author: M.R.B. Clarke]
• A partitioning algorithm for minimum weighted euclidean matching Information Processing Letters 18, 59-62. [Co-author: M.E.Dyer]
• Linear congruential generators do not produce random sequences Proceedings of 25th IEEE Conference on the Foundations of Computer Science, 480-484. [Co-authors: R.Kannan and J.C.Lagarias] JOURNAL VERSION
• Long cycles in sparse random graphs Graph theory and combinatorics, 59-64. Proceedings of Cambridge Combinatorial Conference in honour of Paul Erdos. [Co-authors: B.Bollobas and T.I.Fenner]
• Algebraic flows Annals of Discrete Mathematics 19, 135-146.
• Hamiltonian cycles in random regular graphs Journal of Combinatorial Theory, Series B, 103-112. [Co-author: T.I. Fenner]
• On the existence of polychromatic sets of edges in graphs and digraphs Progress in Graph Theory, Edited by J.A. Bondy and U.S.R. Murty, Academic Press, 219-232. [Co-author: T.I. Fenner]
• Partitioning heuristics for two geometric maximisation problems Operations Research Letters 3, 267-270. [Co-authors: M.E. Dyer and C.J.H. Mc.Diarmid]
• On the quadratic assignment problem Discrete Applied Mathematics 5, 89-98. [Co-author: J. Yadegar]
• An extension of Christofides Heuristic to the k-person travelling salesman problem Discrete Applied Mathematics 6, 79-83.
• On the existence of hamiltonian cycles in a class of random graphs Discrete Mathematics 45, 301-305. [Co-author: T.I. Fenner]
• Complexity of a 3-dimensional assignment problem European Journal of Operational Research 13, 161-164.
• On the worst-case performance of some algorithms for the asymmetric travelling salesman problem Networks 12, 23-39. [Co-authors: G. Galbiati, F. Maffioli]
• Algebraic linear programming Mathematics of Operations Research 7, 172-182.
• K-Greedy Algorithms Proceedings of CO81 Conference on Combinatorial Optimisation, Stirling 66-83.
• On the connectivity of random m-orientable graphs and digraphs Combinatorica 2, 347-359. [Co-author: T.I. Fenner]
• An algorithm for solving 3-dimensional assignment problems with application to scheduling a teaching practice Journal of the Operational Research Society 32, 989-995. [Co-author: J. Yadegar]
• Probabilistic analysis of some Euclidean clustering problems Discrete Applied Mathematics 2, 295-309.
• Worst-case analysis of algorithms for travelling salesman problems Methods of Operations Research 32, 93-112.
• An algorithm for algebraic assignment problems Discrete Applied Mathematics 1, 253-259.
• A partitioned inverse in linear programming Journal of the Operational Research Society 29, 383-388.
• Minimum paths in directed graphs Operational Research Quarterly 28, 339-346.
• A generalisation of the greedy algorithm for matroids Proceedings of CP77, Conference on Combinatorial Programming at Liverpool University.
• Shortest path algorithms for knapsack type problems Mathematical Programming 11, 150-157.
• Bottleneck linear programming Operational Research Quarterly 26, 871-874.
• A cost function property for plant location problems Mathematical Programming 7, 245-248.
• A bilinear programming formulation of the 3-dimensional assignment problem Mathematical Programming 7, 376-379.

Papers (with pdf links to recent ones)

Preprints/submitted (comments are welcome).

• Inducibility of rainbow graphs (with Emily Cairncross, Clayton Mizgerd) (27 pages)
• Big line or big convex polygon (with David Conlon, Jacob Fox, Xiaoyu He, Andrew Suk, Jacques Verstraete) (11 pages)
• A question of Erdos and Graham on Egyptian fractions (with David Conlon, Jacob Fox, Xiaoyu He, Huy Tuan Pham, Andrew Suk, Jacques Verstraete) (8 pages)
• On off-diagonal hypergraph Ramsey numbers (with David Conlon, Jacob Fox, Ben Gunby, Xiaoyu He, Andrew Suk, Jacques Verstraete) (22 pages)
• Ordered and colored subgraph density problems (with Emily Cairncross) (17 pages)
• Improved upper bounds on Erdos-Rogers functions (with Jacques Verstraete) (14 pages)
• Random Turan theorem for hypergraph cycles (with L. Yepremyan) (16 pages)
• Turan problems in pseudorandom graphs (with Xizhi Liu and David Munha Correia) Combin. Probab. Comput. (16 pages)
• Large cliques or co-cliques in hypergraphs with forbidden order-size pairs (with Maria Axenovich, Domagoj Bradac, Lior Gishboliner, Lea Weber) Combin. Probab. Comput. (17 pages)
• Set-coloring Ramsey numbers via codes (with David Conlon, Jacob Fox, Xiaoyu He, Andrew Suk, Jacques Verstraete) Studia Scientiarum Mathematicarum Hungarica. (11 pages)
• Hypergraphs with many extremal configurations (with X. Liu, C. Reiher) Israel. J. Math. (34 pages)
• Ramsey theory constructions from hypergraph matchings (with Felix Joos) Proc. Amer. Math. Soc. (11 pages)
• Ramsey numbers and the Zarankiewicz problem (with David Conlon, Sam Mattheus, Jacques Verstraete) Bull. Lond. Math. Soc. (2024), https://doi.org/10.1112/blms.13040
• A note on pseudorandom Ramsey graphs (with J. Verstraete) J. Eur. Math. Soc. (JEMS) 26 (2024), no. 1, 153-161. See here for an article in Quanta magazine that mentions this work
• Coloring hypergraphs that are the union of nearly disjoint cliques (with Jacques Verstraete) Mathematika 70 (2024), no. 1, Paper No. e12234, 12 pp.
• Ramsey numbers of cliques versus monotone paths (with Andrew Suk) European J. Combin. 118 (2024), 103922.
• Hypergraphs with infinitely many extremal constructions (with Jianfeng Hou, Heng Li, Xizhi Liu, Yixiao Zhang) Discrete Analysis (2023), Paper No. 18, 34 pp.
• Extremal problems for hypergraph blowups of trees (with Z. Furedi, T. Jiang, A. Kostochka, J. Verstraete) SIAM J. Discrete Math. 37 (2023), no. 4, 2397--2416.
• Hypergraph Ramsey numbers of cliques versus stars (with David Conlon, Jacob Fox, Xiaoyu He, Andrew Suk, Jacques Verstraete) Random Structures Algorithms 63 (2023), no. 3, 610--623.
• Triangles in graphs without bipartite suspensions (with S. Mukherjee) Discrete Math. 346 (2023), no. 6, Paper No. 113355, 19 pp.
• The feasible region of induced graphs (with X. Liu, C. Reiher) J. Combin. Theory Ser. B 158 (2023), 105--135.
• A unified approach to hypergraph stability (with X. Liu, C. Reiher) J. Combin. Theory Ser. B 158 (2023), 36--62.
• A hypergraph Turan problem with no stability (with X. Liu) Combinatorica 42 (2022), no. 3, 433--462.
• Independent sets in hypergraphs omitting an intersection (with T. Bohman, X. Liu) Random Structures Algorithms 61 (2022), no. 3, 493--519.
• A note on the Erdos-Hajnal hypergraph Ramsey problem (with A. Suk, E. Zhu) Proc. Amer. Math. Soc. 150 (2022), no. 9, 3675--3685
• On a generalized Erdos-Rademacher problem (with X. Liu) J. Graph Theory 100 (2022), no. 1, 101--126.
• On explicit constructions of designs (with X. Liu) Electron. J. Combin. 29 (2022), no. 1, Paper No. 1.53, 11 pp.
• Extremal problems for pairs of triangles in a convex polygon (with Z. Furedi, J. O'Neill, J. Verstraete) J. Combin. Theory Ser. B 155 (2022), 83--110
• Polynomial to exponential transition in Ramsey theory (with A. Razborov) Proc. Lond. Math. Soc. (3) 122 (2021), no. 1, 69--92.
• Cliques with many colors in triple systems (with A. Suk) J. Comb. (2021), no. 4, 563--569.
• Extremal problems for convex geometric hypergraphs and ordered hypergraphs (with Z. Furedi, T. Jiang, A. Kostochka, J. Verstraete) Canad. J. Math. 73 (2021), no. 6, 1648--1666.
• Maximum H-free subgraphs (with S. Mukherjee) J. Comb. 12 (2021), no. 2, 185--214.
• Tight bounds for Katona's shadow intersection theorem (with X. Liu) European J. Combin. 97 (2021), Paper No. 103391, 17 pp.
• The feasible region of hypergraphs (with X. Liu) J. Combin. Theory Ser. B 148 (2021), 23--59.
• Partitioning ordered hypergraphs (with Z. Furedi, T. Jiang, A. Kostochka, J. Verstraete) J. Combin. Theory Ser. A 177 (2021), 105300, 18pp.
• The Erdos-Hajnal hypergraph Ramsey problem (with A. Suk) J. Eur. Math. Soc. (JEMS) 22 (2020), no. 4, 1247--1259
• A survey of hypergraph Ramsey problems (with A. Suk) Discrete mathematics and applications, 405--428, Springer Optim. Appl., 165, Springer, Cham, [2020],
• Extremal theory of locally sparse multigraphs (with C. Terry) SIAM J. Discrete Math. 34 (2020), no. 3, 1922--1943.
• Ordered and convex geometric trees with linear extremal function (with Z. Furedi, A. Kostochka, J. Verstraete) Discrete Comput. Geom. (2020), no. 2, 324--338 (Branko Grunbaum memorial volume)
• Tight paths in convex geometric hypergraphs (with Z. Furedi, T. Jiang, A. Kostochka, J. Verstraete) Adv. Comb. 2020, Paper No. 1--13, www.advancesincombinatorics.com
• Hypergraphs not containing a tight tree with a bounded trunk II: 3-trees with a trunk of size 2 (with Z. Furedi, T. Jiang, A. Kostochka, J. Verstraete) Discrete Appl. Math. 276 (2020), 50--59.
• Discrete metric spaces: structure, enumeration, and 0-1 laws (with C. Terry) Journal of Symbolic Logic 84 (2019), no. 4, 1293--1325.
• The number of triple systems without even cycles (with L. Wang) Combinatorica 39 (2019), no. 3, 679--704.
• Independence number of graphs with a prescribed number of cliques (with T. Bohman) Electron. J. Combin. 26 (2019), no. 2, Paper 2.25, 7 pp.
• Hypergraphs not containing a tight tree with a bounded trunk (with Z. Furedi, T. Jiang, A. Kostochka, J. Verstraete) SIAM J. Discrete Math. 33 (2019), no. 2, 862--873.
• The Erdos-Szekeres problem and an induced Ramsey question (with A. Suk) Mathematika 65 (2019), no. 3, 702--707
• An extremal graph problem with a transcendental solution (with C. Terry) Combin. Probab. Comput. 28 (2019), no. 2, 303--324
• Multicolor sunflowers (with L. Wang) Combin. Probab. Comput. 27 (2018), no. 6, 974--987.
• New lower bounds for hypergraph Ramsey numbers (with A. Suk) Bull. Lond. Math. Soc. 50 (2018), no. 2, 189--201
• Constructions in Ramsey theory (with A. Suk) J. Lond. Math. Soc. (2) 97 (2018), no. 2, 247--257.
• On the size-Ramsey number of hypergraphs (with A. Dudek, S. La-Fleur, V. Rodl) J. Graph Theory 86 (2017), no. 1, 104--121
• Off-diagonal hypergraph Ramsey numbers (with A. Suk) J. Combin. Theory Ser. B 125 (2017), 168--177.
• The structure of large intersecting families (with A. Kostochka) Proc. Amer. Math. Soc. 145 (2017), no. 6, 2311--2321.
• Sparse hypergraphs with low independence number (with J. Cooper) Combinatorica 37 (2017), no. 1, 31--40
• Variants of the Erdos-Szekeres and Erdos-Hajnal Ramsey problems European J. Combin. 62 (2017), 197--205.
• Eigenvalues of non-regular linear-quasirandom hypergraphs (with J. Lenz) Discrete Math. 340 (2017), no. 2, 145--153.
• Turan problems and shadows II: trees (with A. Kostochka, J. Verstraete) J. Combin. Theory Ser. B 122 (2017), 457--478.
• Coloring triple systems with local conditions J. Graph Theory 81 (2016), no. 3, 307--311.
• A survey of Turan problems for expansions (with J. Verstraete) Recent trends in combinatorics, 117--143, IMA Vol. Math. Appl., 159, Springer, New York, 2016. Vii 706. ISBN: 978-3-319-24296-5.
• The independent neighborhoods process (with T. Bohman, M. Picollelli) Israel J. Math. 214 (2016), no. 1, 333--357.
• Hamilton cycles in quasirandom hypergraphs (with J. Lenz, R. Mycroft) Random Structures Algorithms 49 (2016), no. 2, 363-378
• Improved bounds for the Ramsey number of tight cycles versus cliques Combin. Probab. Comput. 25 (2016), no. 5, 791--796
• Counting trees in graphs (with J. Verstraete) Electron. J. Combin. 23 (3) (2016), #P3.39
• Coloring sparse hypergraphs (with J. Cooper) SIAM J. Discrete Math. 30 (2016), no. 2, 1165--1180.
• Perfect Packings in Quasirandom Hypergraphs II (with J. Lenz) Combin. Probab. Comput. 25 (2016), no. 4, 595--611
• Perfect Packings in Quasirandom Hypergraphs I (with J. Lenz) J. Combin. Theory Ser. B 119 (2016), 155--177.
• Inverse Expander Mixing for Hypergraphs (with E. Cohen, P. Ralli, P. Tetali) Electron. J. Combin. 23 (2) (2016), #P2.20
• Hypergraph Ramsey numbers: tight cycles versus cliques (with V. Rodl) Bull. Lond. Math. Soc. 48 (2016), no. 1, 127--134.
• On the chromatic thresholds of hypergraphs (with J. Balogh, J. Butterfield, P. Hu, J. Lenz) Combin. Probab. Comput. 25 (2016), no. 2, 172--212.
• List Coloring Triangle-Free Hypergraphs (with J. Cooper) Random Structures and Algorithms 47 (2015), no. 3, 487--519
• The poset of hypergraph quasirandomness (with J. Lenz) Random Structures and Algorithms 46 (2015), no. 4, 762--800
• Turan problems and shadows III: expansions of graphs (with A. Kostochka, J. Verstraete) SIAM Journal on Discrete Mathematics 29 (2015), no. 2, 868--876.
• Eigenvalues and linear quasirandom hypergraphs (with J. Lenz) Forum of Mathematics, Sigma (2015), Vol. 3, e2, 26 pages
• Turan Problems and Shadows I: Paths and Cycles (with A. Kostochka, J. Verstraete) Journal of Combinatorial Theory, Series A 129 (2015), 57--79.
• Spectral extremal problems for hypergraphs (with P. Keevash, J. Lenz) Siam Journal on Discrete Mathematics 28 (2014), no. 4, 1838.1854.
• Counting independent sets in hypergraphs (with J. Cooper, K. Dutta) Combinatorics, Probability and Computing 23 (2014), no. 4, 539.550.
• A Ramsey-type result for geometric l-hypergraphs (with A. Suk) European Journal of Combinatorics 41 (2014), 232-241 and Graph drawing, 364-375, Lecture Notes in Comput. Sci., 8242, Springer, Cham, 2013.
• Multicolor Ramsey numbers for complete bipartite versus complete graphs (with J. Lenz) Journal of Graph Theory 77 (2014), no. 1, 19.38.
• On generalized Ramsey numbers for 3-uniform hypergraphs (with A. Dudek) Journal of Graph Theory 76 (2014), no. 3, 217.223.
• Counting independent sets in triangle-free graphs (with J. Cooper), Proceedings of the American Mathematical Society 142 (2014), no. 10, 3325.3334.
• On independent sets in hypergraphs (with A. Kostochka, J. Verstraete), Random Structures and Algorithms 44 (2014), no. 2, 224.239.
• Multicolor Ramsey numbers for triple systems (with M. Axenovich, A. Gyarfas, H. Liu) Discrete Math. 322 (2014), 69--77.
• Specified Intersections (with V. Rodl), Transactions of the American Mathematical Society 366 (2014), no. 1, 491.504.
• Counting substructures II: hypergraphs , Combinatorica 33 (2013), no. 5, 591.612. (57 pages) (Journal version is shorter with no Appendix)
• Coloring simple hypergraphs (with A. Frieze) Journal of Combinatorial Theory, Series B 103 (2013), no. 6, 767.794.
• Coloring the cube with rainbow cycles (with R. Stading), Electronic Journal of Combinatorics (2013), no. 2, Paper 4, 11 pp.
• New lower bounds for the independence number of spars e graphs and hypergraphs (with K. Dutta, C.R. Subramanian), SIAM Journal on Discrete Math 26 (2012), no. 3, 1134–1147.
• Tree-minimal graphs are almost regular (with D. Dellamonica Jr., P. Haxell, T. Luczak, B. Nagle, Y. Person, V. Rodl, M. Schacht), Journal of Combinatorics 3 (2012), no. 1, 49–62.
• On even-degree subgraphs of linear hypergraphs (with D. Dellamonica, P. Haxell, T. Luczak, B. Nagle, Y. Person, V. Rodl, M. Schacht, J. Verstraete), Combinatorics, Probability and Computing 21 (2012), no. 1-2, 113–127
• The de Bruijn-Erdos Theorem for hypergraphs (with N. Alon, K. Mellinger, J. Verstraete), Designs, Codes and Cryptography, 65, (2012) no. , 233--2453
• Books versus Triangles , Journal of Graph Theory 70 (2012), no. 2, 171--179.
• The Turan number of F33 (with P. Keevash), Combinatorics, Probability and Computing 21 (2012), no. 3, 451--456.
• Almost all triangle-free triple systems are tripartite (with J. Balogh), Combinatorica 32 (2012), no. 2, 143-169.
• Two-part set systems (with P. Erdos, D. Gerbner, N. Lemons, C. Palmer, B. Patkos), Electronic Journal of Combinatorics, 19 (2012) p 52
• Almost all triple systems with independent neighborhoods are semi-bipartite (with J. Balogh), Journal of Combinatorial Theory, Series A, 118 (2011), no. 4, 1494-1518
• Counting substructures I: color critical graphs , Advances in Mathematics 225 (2010) 2731-2740
• Hypergraphs with independent neighborhoods (with T. Bohman, A. Frieze, O. Pikhurko), Combinatorica 30 (2010), no. 3, 277-293
• Set systems without a simplex or a cluster (with P. Keevash), Combinatorica 30 (2010), no. 2, 175-200
• On Approximate Horn Formula Minimization (with A. Bhattacharya, B. Dasgupta, G. Turan), ICALP 2010 (21 pages)
• Finding bipartite subgraphs efficiently (with G. Turan), Information Processing Letters, Volume 110, Issue 5, 1 February 2010, Pages 174-177
• Coloring H-free hypergraphs (with T. Bohman, A. Frieze), Random Structures and Algorithms 36 (2010) 11-25.
• Bipartite Coverings and the Chromatic Number (with S. Vishwanathan), Electronic Journal of Combinatorics, 16 (2009), #N34
• Combinatorial problems for horn clauses (with M. Langlois, R. Sloan, G. Turan), in: Graph Theory, Computational Intelligence and Thought (M.Lipshteyn, V.E.Levit, R.M.McConnell, eds.), Springer LNCS 5420, 2009, 54-65.
• Erdos-Ko-Rado in Random Hypergraphs (with J. Balogh, T. Bohman ), Combinatorics, Probability and Computing 18 (2009), no. 5, 629--646 (Special issue in honor of Tom Trotters 60th birthday)
• Simplex stability (with R. Ramadurai), Combinatorics, Probability and Computing 18 (2009), no. 3, 441--454.
• Two-regular subgraphs of hypergraphs (with J. Verstraete), Journal of Combinatorial Theory, Series B 99 (2009), no. 3, 643--655.
• Set systems with union and intersection constraints (with R. Ramadurai), Journal of Combinatorial Theory, Series B 99 (2009), no. 3, 639--642
• Quadruple systems with independent neighborhoods (with Z. Furedi and O. Pikhurko), Journal of Combinatorial Theory, Series A 115 (2008), no. 8, 1552--1560.
• On the chromatic number of simple triangle-free triple systems (with A. Frieze), Electronic Journal of Combinatorics 15 (2008), no. 1, Research Paper 121, 27 pp.
• When is an almost monochromatic K4 guaranteed? (with A. Kostochka), Combinatorics, Probability and Computing 17, (2008), no. 6, 823-830
• Constructions of nonprincipal families in extremal hypergraph theory (with O. Pikhurko), Discrete Mathematics, 308 (2008), no. 19, 4430--4434
• Extremal problems for t-partite and t-colorable hypergraphs (with J. Talbot), Electronic Journal of Combinatorics 15 (2008), no. 1, Research Paper 26, 9 pp
• A new short proof of a theorem of Ahlswede and Khachatrian (with J. Balogh), Journal of Combinatorial Theory, Series A, 115 (2008), no. 2, 326--330
• Forbidding complete hypergraphs as traces (with Y. Zhao), Graphs and Combinatorics, 23 (2007), no. 6, 667--679
• Minimal paths and cycles in set-systems (with J. Verstraete), European Journal of Combinatorics, 28 (2007) no.6, 1681--1693
• Co-degree density of hypergraphs (with Y. Zhao), Journal of Combinatorial Theory, Series A, 114 (2007), no. 6, 1118--1132
• A new generalization of Mantel's theorem to k-graphs (with O. Pikhurko), Journal of Combinatorial Theory, Series B, 97 (2007), no. 4, 669--678
• On the independence number of the Erdos-Renyi and Projective Norm graphs and a related hypergraph (with J. Williford), Journal of Graph Theory 56 (2007), no. 2, 113--127
• Efficient Algorithms for the Inverse Protein Folding Problem on 2D and 3D Lattices (with P. Berman, B. DasGupta, R. H. Sloan, G. Turan, Y. Zhang), Discrete Applied Mathematics, 155 (2007), no. 6-7, 719--732.
• On the VC-dimension of uniform hypergraphs (with Y. Zhao), Journal of Algebraic Combinatorics, 25 (2007), no. 1, 101--110
• On the chromatic number and independence number of hypergraph products (with V. Rodl), Journal of Combinatorial Theory, Series B, 97 (2007), no. 1, 151--155
• Rainbow Turan Problems (with P. Keevash, B. Sudakov, J. Verstraete), Combinatorics Probability and Computing 16 (2007), 109--126. Erratum to this paper.
• Structure and stability of triangle-free set systems , Transactions of the American Mathematical Society, 359 (2007), 275-291.
• Set systems with no singleton intersection (with P. Keevash and R. Wilson), SIAM Journal on Discrete Mathematics 20 (2006), no. 4, 1031--1041.
• On the edge-bandwidth of graph products (with J. Balogh, A. Pluhar), Theoretical Computer Science, 359 (2006) 43--57
• Supersaturation for Ramsey-Turan Problems (with V. Rodl), Combinatorica, 26 (2006), no. 3, 315--332
• Explicit constructions of triple systems for Ramsey-Turan problems (with V. T. Sos), Journal of Graph Theory, 52 (2006), no. 3, 211--216
• Erdos-Ko-Rado for three sets , Journal of Combinatorial Theory, Series A, 113 (2006), no. 3, 547--550 (the journal version has some minor typos in it, involving the characterization of equality in Frankl's theorem and the Erdos-Ko-Rado theorem. These are corrected in the version posted here)
• The DNF Exception Problem (with G. Turan, Y. Zhao), Theoretical Computer Science, 352 (2006), no. 1-3, 85--96.
• A hypergraph extension of Turan's theorem , Journal of Combinatorial Theory, Series B, 96 (2006), no. 1, 122--134
• Proof of a conjecture of Erdos on triangles in set systems (with J. Verstraete), Combinatorica, 25 (2005), no. 5, 599--614
• The co-degree density of the Fano plane , Journal of Combinatorial Theory, Series B, 95 (2005), no. 2, 333--337
• Nonuniform Turan-type problems (with Y. Zhao), Journal of Combinatorial Theory, Series A, 111 (2005) 106--110
• Constructions of bipartite graphs from finite geometries (with K. Mellinger), Journal of Graph Theory 49 (2005), no. 1, 1--10.
• A family of switch equivalent graphs (with B. Guenin, P. Tetali), Discrete Mathematics 288 (2004), no. 1-3, 29--35.
• Uniform edge distribution in hypergraphs is hereditary (with V. Rodl), Electronic Journal of Combinatorics, 11 (2004), no. 1, Research Paper R55, 32pp. (electronic)
• Stability results for cancellative hypergraphs (with P. Keevash), Journal of Combinatorial Theory, Series B, 92 (2004) 163--175
• An explicit construction for a Ramsey problem , Combinatorica, 24 (2004), no. 2, 313--324
• A hypergraph extension of the Bipartite Turan problem (with J. Verstraete), Journal of Combinatorial Theory, Series A 106 (2004) no. 2, 237--253
• How many disjoint 2-edge paths must a cubic graph have? (with A. Kelmans), Journal of Graph Theory 45 (2004), no. 1, 57-79
• Efficient Algorithms for the Inverse Protein Folding Problem on 2D and 3D Lattices (with P. Berman, B. DasGupta, R. H. Sloan, G. Turan, Y. Zhang), Fifteenth Annual Combinatorial Pattern Matching (CPM) Symposium, LNCS 3109, pp. 244--253, July 2004, and accepted in Discrete Applied Math
• Coloring with three-colored subgraphs , Journal of Graph Theory 42 (2003), no. 3, 193--198
• On hypergraphs with every four points spanning at most two triples , Electronic Journal of Combinatorics, 10 (2003), no. 1, Research Paper N10, 4 pp. (electronic)
• On a two-sided Turan problem (with Y. Zhao), Electronic Journal of Combinatorics, 10 (2003), no. 1, Research Paper R42, 17 pp. (electronic)
• The Chromatic Spectrum of Mixed Hypergraphs (with T. Jiang, Z. Tuza, V. Voloshin, D. B. West), Graphs and Combinatorics, 18 (2002), no. 2, 309--318
• New lower bounds for Ramsey numbers of graphs and hypergraphs (with F. Lazebnik), Advances in Applied Mathematics, 28 (2002), no. 3-4, 544--559
• Some exact results and new asymptotics for hypergraph Turan numbers , Combinatorics, Probability and Computing, 11 (2002), no. 3, 299--309
• On Restricted Edge-Colorings of Bicliques (with D. B. West), Kleitman and combinatorics: a celebration (Cambridge, MA, 1999). Discrete Mathematics (2002), no. 2-3, 513--529
• Generalizing the Ramsey Problem through Diameter , Electronic Journal of Combinatorics, 9 (2002), no. 1, Research Paper 42, 10 pp. (electronic)
• On the Turan number of Triple Systems (with V. Rodl), Journal of Combinatorial Theory, Series A, 100 (2002), no. 1, 136--152
• Intersecting Curves in the Plane , Graphs and Combinatorics, 18 (2002), no. 3, 583--589
• Minimal Completely Separating Systems of k-Sets (with A. Kundgen, P. Tetali), Journal of Combinatorial Theory, Series A, 93 (2001), no. 1, 192--198
• Large induced forests in sparse graphs (with N. Alon, R. Thomas), Journal of Graph Theory, 38 (2001), no. 3, 113--123
• On the chromatic number of set-systems (with A. Kostochka, V. Rodl, P. Tetali), Random Structures and Algorithms, 19 (2001), no. 2, 87--98
• Asymptotically optimal tree-packings in regular graphs (with A. Kelmans, B. Sudakov), Electronic Journal of Combinatorics 8 (2001), no. 1, Research Paper 38, 8 pp. (electronic)
• Realizing Degree Imbalances in Directed Graphs (with D. B. West, T. G. Will), Discrete Mathematics 239 (2001), no. 1-3, 147--153
• Graphic Sequences that have a Realization with Large Clique Number, Journal of Graph Theory, 34 (2000), no. 1, 20--29
• On generalized Ramsey theory: the bipartite case (with M. Axenovich, Z. Furedi), Journal of Combinatorial Theory, Series B, 79 (2000), no. 1, 66--86
• New Upper Bounds for a Canonical Ramsey Problem (with T. Jiang), Combinatorica, 20 (1) (2000) 141--146
• Multiple Vertex Coverings by Specified Induced Subgraphs (with Z. Furedi, D. B. West), Journal of Graph Theory, 34 (2000), no. 2, 180--190
• Edge-Coloring Cliques with Many Colors on Subcliques (with D. Eichhorn), Combinatorica, 20 (3) (2000) 441--444
• Edge-Bandwidth of Theta Graphs (with D. Eichhorn, K. O'Bryant, D. B. West), Journal of Graph Theory, 35 (2000) 89--98
• On the Number of Vertices with Specified Eccentricity (with D. B. West), Graphs and Combinatorics, 16 (4) (2000) 441-452
• Signed Domination in Regular Graphs and Set-Systems, (with Z. Furedi), Journal of Combinatorial Theory, Series B, 76 (1999), no. 2, 223--239
• Edge Bandwidth of Graphs (with T. Jiang, A. Shastri, D. B. West), SIAM Journal on Discrete Mathematics 12 (1999), no. 3, 307--316
• Edge-Coloring Cliques with Three Colors on all 4-cliques, Combinatorica, 18 (1998), no. 2, 293--296
• Connectivity and Separating Sets of Cages (with T. Jiang), Journal of Graph Theory, 29 (1998), no. 1, 35--44

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Recent research in Graph Theory

Related Papers

International Journal of Machine Learning and Cybernetics

Utpal Dasgupta

Mathematics in Computer Science

Marc Hellmuth

Discrete Applied Mathematics

Journal of Graph Theory

Mateja Šajna

In this paper we study fundamental connectivity properties of hypergraphs from a graph-theoretic perspective, with the emphasis on cut edges, cut vertices, and blocks. To prepare the ground, we define various types of subhypergraphs, as well as various types of walks in a hypergraph. We then prove a number of new results involving cut edges, cut vertices, and blocks. In particular, we describe the exact relationship between the block decomposition of a hypergraph and the block decomposition of its incidence graph.

Journal of Combinatorial Theory, Series B

Joshua Cooper

Yeow Meng Chee

Lecture Notes in Computer Science

Arnaud Sallaberry

Giorgio Gallo

arXiv: Combinatorics

Andrew Penland

Graphs and hypergraphs are foundational structures in discrete mathematics. They have many practical applications, including the rapidly developing field of bioinformatics, and more generally, biomathematics. They are also a source of interesting algorithmic problems. In this paper, we define a \textit{construction process} for minimally connected $r$-uniform hypergraphs, which captures the intuitive notion of building a hypergraph piece-by-piece, and a numerical invariant called the \textit{tightness}, which is independent of the construction process used. Using these tools, we prove some fundamental properties of minimally connected hypergraphs. We also give bounds on their chromatic numbers and provide some results involving edge colorings. We show that every connected $r$-uniform hypergraph contains a minimally connected spanning subhypergraph and provide a polynomial-time algorithm for identifying such a subhypergraph.

Loading Preview

Sorry, preview is currently unavailable. You can download the paper by clicking the button above.

RELATED PAPERS

Ars Combinatoria -Waterloo then Winnipeg-

Navin Singhi

Designs, Codes and Cryptography

Jacques Verstraete

Optimization Letters

Samuel Rota Bulò

Czechoslovak Mathematical Journal

Fatemeh Mohammadi

Theory and Applications of Graphs

Imran Javaid

Linear Algebra and its Applications

Bijan Davvaz

Le Centre pour la Communication Scientifique Directe - HAL - ENPC

Lama Tarsissi

Discrete Mathematics

Robert Bailey

Theoretical Computer Science

Khaled Elbassioni

Random Structures and Algorithms

Yulia Dementieva

Tamás Király

Mathematical Programming

Giorgio Gallo , Riccardo Cambini

Electronic Notes in Discrete Mathematics

Deborah Oliveros

andras frank

Sang Nguyen

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

spectral graph theory Recently Published Documents

Total documents.

• Latest Documents
• Most Cited Documents
• Contributed Authors
• Related Sources
• Related Keywords

Discrete Green’s functions and spectral graph theory for computationally efficient thermal modeling

Discover, sample and refine: exploring chemistry with enhanced sampling techniques.

Over the last few decades enhanced sampling methods have made great strides. Here, we exploit this progress and propose a modular workflow for blind reaction discovery and characterization of reaction paths. Central to our strategy is the use of the recently developed explore variant of the on-the-fly probability enhanced sampling method. Like metadynamics, this method is based on the identification of appropriate collective variables. Our first step is the discovery of new chemical reactions and it is performed biasing a one dimensional collective variable derived from spectral graph theory. Once new reaction pathways are detected, we construct ad-hoc tailored neural-network based collective variables to improve sampling of specific reactions and finally we refine the results using free energy perturbation theory. Our workflow has been successfully applied to both intramolecular and intermolecular reactions. Without any chemical hypothesis, we discovered several possible products, computed the free energy surface at semiempirical level, and finally refined it with a more accurate Hamiltonian. Our workflow requires minimal user input, and thanks to its modularity and flexibility, can extend the scope of ab initio molecular dynamics for the exploration and characterization of reaction space.

Geary’s c and Spectral Graph Theory

Spatial autocorrelation, of which Geary’s c has traditionally been a popular measure, is fundamental to spatial science. This paper provides a new perspective on Geary’s c. We discuss this using concepts from spectral graph theory/linear algebraic graph theory. More precisely, we provide three types of representations for it: (a) graph Laplacian representation, (b) graph Fourier transform representation, and (c) Pearson’s correlation coefficient representation. Subsequently, we illustrate that the spatial autocorrelation measured by Geary’s c is positive (resp. negative) if spatially smoother (resp. less smooth) graph Laplacian eigenvectors are dominant. Finally, based on our analysis, we provide a recommendation for applied studies.

Spectral graph theory of brain oscillations -- revisited and improved

Mathematical modeling of the relationship between the functional activity and the structural wiring of the brain has largely been undertaken using non-linear and biophysically detailed mathematical models with regionally varying parameters. While this approach provides us a rich repertoire of multistable dynamics that can be displayed by the brain, it is computationally demanding. Moreover, although neuronal dynamics at the microscopic level are nonlinear and chaotic, it is unclear if such detailed nonlinear models are required to capture the emergent meso- (regional population ensemble) and macro-scale (whole brain) behavior, which is largely deterministic and reproducible across individuals. Indeed, recent modeling effort based on spectral graph theory has shown that an analytical model without regionally varying parameters can capture the empirical magnetoencephalography frequency spectra and the spatial patterns of the alpha and beta frequency bands accurately. In this work, we demonstrate an improved hierarchical, linearized, and analytic spectral graph theory-based model that can capture the frequency spectra obtained from magnetoencephalography recordings of resting healthy subjects. We reformulated the spectral graph theory model in line with classical neural mass models, therefore providing more biologically interpretable parameters, especially at the local scale. We demonstrated that this model performs better than the original model when comparing the spectral correlation of modeled frequency spectra and that obtained from the magnetoencephalography recordings. This model also performs equally well in predicting the spatial patterns of the empirical alpha and beta frequency bands.

Understanding Discrete Fracture Networks Through Spectral Graph Theory

Applications of rational difference equations to spectral graph theory, the network topology metrics contributing to local-area frequency stability in power system networks.

The power system network topology influences the system frequency response to power imbalance disturbances. Here, the objective is to find the network metric(s) contributing to frequency transient stability. The graph Laplacians of six 4-node network topologies are analysed using Spectral Graph Theory. For homogeneous network connections, we show that the node degree measure indicates node robustness. Based on these analytical results, the investigation expands to a 10-node network topology consisting of two clusters, which provide further insight into the spectral results. The research then involves a simulation of a power imbalance disturbance on three 20-node networks with different topologies based on node degree, where we link the node degree measure to imbalance disturbance propagation through Wave Theory. The results provide an intuitive understanding of the impact of network topology on power system frequency stability. The analytical and simulation results indicate that a node’s sensitivity to disturbances is partially due to its node degree, reactance from disturbance location, and the link it has to other higher degree nodes (hierarchical position in network topology). Testing of the analytical and simulation results takes place on the nonhomogeneous IEEE-14 bus and IEEE-39 bus networks. These results provide insights into optimal inertia placement to improve the frequency robustness of low-inertia power systems. The network topology, considering node degrees, influences the speed at which the disturbance impact propagates from the disturbance location and how fast-standing waves form. The topology thus contributes to how fast the energy in a disturbance dissipates to zero.

Hyper-Wiener index for fuzzy graph and its application in share market

Topological indices have an important role in molecular chemistry, network theory, spectral graph theory and several physical worlds. Most of the topological indices are defined in a crisp graph. As fuzzy graphs are more generalization of crisp graphs, those indices have more application in fuzzy graphs also. In this article, we introduced the fuzzy hyper-Wiener index (FHWI) and studied this index for various fuzzy graphs like path, cycle, star, etc and provided some interesting bounds of FHWI for that fuzzy graph. A lower bound of FHWI is established for n-vertex connected fuzzy graph depending on strength of a strong edges. A relation between FHWI of a tree and its maximum spanning tree is established and this index is calculated for the saturated cycle. Also, at the end of the article, an application in the share market of this index is presented.

Spectral Graph Theory Based Resource Allocation for IRS-Assisted Multi-Hop Edge Computing

Export citation format, share document.

• DOI: 10.1088/1742-6596/2728/1/012077
• Corpus ID: 268593221

Power system topological node tamper detection method based on fuzzy graph theory

• Huijuan Tan , Wenxin Guo , +2 authors Qian Li
• Published in Journal of Physics… 1 March 2024
• Engineering, Computer Science
• Journal of Physics: Conference Series

8 References

Intersecting near-optimal spaces: european power systems with more resilience to weather variability, degree distributions under general node removal: power-law or poisson, continual representation learning for node classification in power-law graphs, enhancing the power grid robustness against cascading failures under node-based attacks, architecture of a residential solid state power substation (ssps) node, wearable low-power bio-signals wireless sensing node design, related papers.

Showing 1 through 3 of 0 Related Papers

share this!

June 18, 2024

This article has been reviewed according to Science X's editorial process and policies . Editors have highlighted the following attributes while ensuring the content's credibility:

fact-checked

peer-reviewed publication

trusted source

New theory broadens phase transition exploration

by Los Alamos National Laboratory

In a paper recently published in Physical Review Letters , Los Alamos National Laboratory researchers offer a new theory that predicts defect density across a variety of phase transitions. The research opens new routes for the exploration of defect formation in fields such as materials science, high-energy physics and cosmology.

"Phase transitions are a part of everyday life as well as fundamental phenomena in high-energy physics, inevitable in the early universe ," said Fumika Suzuki, Los Alamos scientist and lead author on the paper. "Our study demonstrates that, when integrated with nucleation theory, the Kibble-Zurek mechanism proposed for second-order, or continuous, phase transitions can be extended to predict defect formation in a wider range of phase transitions."

First- and second-order phase transitions

In first-order phase transitions, some parts of a system may enter the new phase before other parts—think of water boiling, with vapor bubbles forming as the water boils away. In second-order transitions, an entire system transitions at once. Systems such as superconductors and charged superfluids can experience second-order phase transitions that under the influence of external parameters (such as temperature or field) can develop first-order characteristics.

The Kibble-Zurek mechanism, co-named for Los Alamos physicist and paper co-author Wojciech Zurek, predicts the density of topological defects formed due to phase transitions, applying originally only to the second-order phase transitions.

But by integrating the Kibble-Zurek mechanism with nucleation theory, which describes the dynamics of symmetry breaking in first-order phase transitions, Suzuki and Zurek could extend the Kibble-Zurek mechanism to predict the density of defects formed in "tunable" phase transitions that combine characteristics of the phase transitions of first and second order.

The team's theory could be tested, for example, in the Fredericks phase transition in liquid crystals, which can be continuously tuned between first order and second order.

Journal information: Physical Review Letters , arXiv

Provided by Los Alamos National Laboratory

Explore further

Feedback to editors

Look to women for sustainable livestock farming bordering the Amazon rainforest, says study

2 hours ago

New study finds at least 1 in 4 US residential yards exceeds new EPA lead soil level guideline

3 hours ago

Biologists take closer look at stress response in cells

4 hours ago

City sprawl is now large enough to sway global warming over land

Physicists combine multiple Higgs boson pair studies and discover clues about the stability of the universe

6 hours ago

Anti-Asian rhetoric during the pandemic negatively impacted employment and earnings, new research finds

New method enhances X-ray microscopy for detecting tiny defects

New technique achieves visualization of instantaneous states of materials in high-speed devices

Team of biologists discover fluorescence in 27 marine creatures

Study reveals huge increase in global economic cost of invasive mosquitoes and diseases they transmit

Relevant physicsforums posts, gravity & organic matter.

9 hours ago

Researchers find experimental evidence for a graviton-like particle

Jun 13, 2024

How to Calculate electron temperature of Arc Plasma?

Jun 11, 2024

Could you use the Moon to reflect sunlight onto a solar sail?

Jun 10, 2024

List of Verdet Constants?

May 31, 2024

Discussion about least squares method

May 29, 2024

More from Other Physics Topics

Related Stories

The Kibble-Zurek mechanism for nonequilibrium phase transitions

Nov 30, 2022

Utilizing scanning SQUID microscopy to investigate local magnetic response of Bi2212

May 16, 2024

Terahertz flexible multiplexing chip enabled by synthetic topological phase transitions

May 8, 2024

Researchers answer fundamental question of quantum physics

Sep 22, 2022

Towards quantum simulation of false vacuum decay

Jan 20, 2022

Researchers realize the quantum simulations of topological phase transitions

Jan 5, 2023

Recommended for you

A method to reversibly control Casimir forces using external magnetic fields

12 hours ago

Physicists find a new way to represent π

10 hours ago

Researchers observe a large anomalous Hall effect triggered by spin-fluctuating devil's staircase

Scientists develop 3D printed vacuum system that aims to trap dark matter

Jun 17, 2024

Quantum entangled photons react to Earth's spin

Jun 14, 2024

Let us know if there is a problem with our content

Use this form if you have come across a typo, inaccuracy or would like to send an edit request for the content on this page. For general inquiries, please use our contact form . For general feedback, use the public comments section below (please adhere to guidelines ).

Please select the most appropriate category to facilitate processing of your request

Thank you for taking time to provide your feedback to the editors.

Your feedback is important to us. However, we do not guarantee individual replies due to the high volume of messages.

E-mail the story

Your email address is used only to let the recipient know who sent the email. Neither your address nor the recipient's address will be used for any other purpose. The information you enter will appear in your e-mail message and is not retained by Phys.org in any form.

Newsletter sign up

Get weekly and/or daily updates delivered to your inbox. You can unsubscribe at any time and we'll never share your details to third parties.

More information Privacy policy

Donate and enjoy an ad-free experience

We keep our content available to everyone. Consider supporting Science X's mission by getting a premium account.

E-mail newsletter

Harvard Scientists Say There May Be an Unknown, Technologically Advanced Civilization Hiding on Earth

A provocative hypothesis..

What if — stick with us here — an unknown technological civilization is hiding right here on Earth, sheltering in bases deep underground and possibly even emerging with UFOs or disguised as everyday humans?

In a new paper that's bound to raise eyebrows in the scientific community, a team of researchers from Harvard and Montana Technological University speculates that sightings of "Unidentified Anomalous Phemonemona" (UAP) —  bureaucracy-speak for UFOs, basically — "may reflect activities of intelligent beings concealed in stealth here on Earth (e.g., underground), and/or its near environs (e.g., the Moon), and/or even 'walking among us' (e.g., passing as humans)."

Yes, that's a direct quote from the paper. Needless to say, the researchers admit, this idea of hidden "crypoterrestrials" is a highly exotic hypothesis that's "likely to be regarded skeptically by most scientists." Nonetheless, they argue, the theory "deserves genuine consideration in a spirit of epistemic humility and openness."

The interest in unexplained sightings of UFOs by military personnel has grown considerably over the past decade or so. This attention grew to a peak last summer, when former Air Force intelligence officer and whistleblower David Grusch testified in front of Congress , claiming that the US had already recovered alien spacecraft as part of a decades-long UFO retrieval program.

Even NASA has opened its doors for researchers to explore mysterious, high-speed objects that have been spotted by military pilots over the years.

But several Pentagon reports later, we have yet to find any evidence of extraterrestrial life.

That hasn't dissuaded these Harvard researchers, though. In the paper, they suggest a range of possibilities, each more outlandish than the next.

First is that a "remnant form" of an ancient, highly advanced human civilization is still hanging around, observing us. Second is that an intelligent species evolved independently of humans in the distant past, possibly from "intelligent dinosaurs," and is now hiding their presence from us. Third is that these hidden occupants of Earth traveled here from another planet or time period. And fourth — please keep a straight face, everybody — is that these unknown inhabitants of Earth are "less technological than magical," which the researchers liken to "earthbound angels."

UFO sightings of "craft and other phenomena (e.g., 'orbs') appearing to enter/exit potential underground access points, like volcanoes," they write, could be evidence that these cryptoterrestrials may not be drawn to these spots, but actually reside in underground or underwater bases.

The paper quotes former House Representative Mike Gallagher, who suggested last year that one explanation for the UFO sightings might be "an ancient civilization that’s just been hiding here, for all this time, and is suddenly showing itself right now," following Grusch's testimony.

The researchers didn't stop there, even suggesting that these cryptoterrestrials may take on different, non-human primate or even reptile forms.

Beyond residing deep underground, they even speculate that this mysterious species could even be concealing themselves on the Moon or have mastered the art of blending in as human beings, a folk theory that has inspired countless works of science fiction.

Another explanation, as put forward by controversial Harvard astrophysicist Avi Loeb, suggests that other ancient civilizations may have lived on "planets like Mars or Earth" but a "billion years apart and hence were not aware of each other."

Of course, these are all "far-fetched" hypotheses, as the scientists admit, and deserve to be regarded with plenty of skepticism.

"We entertain them here because some aspects of UAP are strange enough that they seem to call for unconventional explanations," the paper reads.

"It may be exceedingly improbable, but hopefully this paper has shown it should nevertheless be kept on the table as we seek to understand the ongoing empirical mystery of UAP," the researchers conclude.

More on UFOs: New Law Would Force Government to Declassify Every UFO Document

Share This Article

The state of AI in early 2024: Gen AI adoption spikes and starts to generate value

If 2023 was the year the world discovered generative AI (gen AI) , 2024 is the year organizations truly began using—and deriving business value from—this new technology. In the latest McKinsey Global Survey  on AI, 65 percent of respondents report that their organizations are regularly using gen AI, nearly double the percentage from our previous survey just ten months ago. Respondents’ expectations for gen AI’s impact remain as high as they were last year , with three-quarters predicting that gen AI will lead to significant or disruptive change in their industries in the years ahead.

About the authors

This article is a collaborative effort by Alex Singla , Alexander Sukharevsky , Lareina Yee , and Michael Chui , with Bryce Hall , representing views from QuantumBlack, AI by McKinsey, and McKinsey Digital.

Organizations are already seeing material benefits from gen AI use, reporting both cost decreases and revenue jumps in the business units deploying the technology. The survey also provides insights into the kinds of risks presented by gen AI—most notably, inaccuracy—as well as the emerging practices of top performers to mitigate those challenges and capture value.

AI adoption surges

Interest in generative AI has also brightened the spotlight on a broader set of AI capabilities. For the past six years, AI adoption by respondents’ organizations has hovered at about 50 percent. This year, the survey finds that adoption has jumped to 72 percent (Exhibit 1). And the interest is truly global in scope. Our 2023 survey found that AI adoption did not reach 66 percent in any region; however, this year more than two-thirds of respondents in nearly every region say their organizations are using AI. 1 Organizations based in Central and South America are the exception, with 58 percent of respondents working for organizations based in Central and South America reporting AI adoption. Looking by industry, the biggest increase in adoption can be found in professional services. 2 Includes respondents working for organizations focused on human resources, legal services, management consulting, market research, R&D, tax preparation, and training.

Also, responses suggest that companies are now using AI in more parts of the business. Half of respondents say their organizations have adopted AI in two or more business functions, up from less than a third of respondents in 2023 (Exhibit 2).

Gen AI adoption is most common in the functions where it can create the most value

Most respondents now report that their organizations—and they as individuals—are using gen AI. Sixty-five percent of respondents say their organizations are regularly using gen AI in at least one business function, up from one-third last year. The average organization using gen AI is doing so in two functions, most often in marketing and sales and in product and service development—two functions in which previous research  determined that gen AI adoption could generate the most value 3 “ The economic potential of generative AI: The next productivity frontier ,” McKinsey, June 14, 2023. —as well as in IT (Exhibit 3). The biggest increase from 2023 is found in marketing and sales, where reported adoption has more than doubled. Yet across functions, only two use cases, both within marketing and sales, are reported by 15 percent or more of respondents.

Gen AI also is weaving its way into respondents’ personal lives. Compared with 2023, respondents are much more likely to be using gen AI at work and even more likely to be using gen AI both at work and in their personal lives (Exhibit 4). The survey finds upticks in gen AI use across all regions, with the largest increases in Asia–Pacific and Greater China. Respondents at the highest seniority levels, meanwhile, show larger jumps in the use of gen Al tools for work and outside of work compared with their midlevel-management peers. Looking at specific industries, respondents working in energy and materials and in professional services report the largest increase in gen AI use.

Investments in gen AI and analytical AI are beginning to create value

The latest survey also shows how different industries are budgeting for gen AI. Responses suggest that, in many industries, organizations are about equally as likely to be investing more than 5 percent of their digital budgets in gen AI as they are in nongenerative, analytical-AI solutions (Exhibit 5). Yet in most industries, larger shares of respondents report that their organizations spend more than 20 percent on analytical AI than on gen AI. Looking ahead, most respondents—67 percent—expect their organizations to invest more in AI over the next three years.

Where are those investments paying off? For the first time, our latest survey explored the value created by gen AI use by business function. The function in which the largest share of respondents report seeing cost decreases is human resources. Respondents most commonly report meaningful revenue increases (of more than 5 percent) in supply chain and inventory management (Exhibit 6). For analytical AI, respondents most often report seeing cost benefits in service operations—in line with what we found last year —as well as meaningful revenue increases from AI use in marketing and sales.

Inaccuracy: The most recognized and experienced risk of gen AI use

As businesses begin to see the benefits of gen AI, they’re also recognizing the diverse risks associated with the technology. These can range from data management risks such as data privacy, bias, or intellectual property (IP) infringement to model management risks, which tend to focus on inaccurate output or lack of explainability. A third big risk category is security and incorrect use.

Respondents to the latest survey are more likely than they were last year to say their organizations consider inaccuracy and IP infringement to be relevant to their use of gen AI, and about half continue to view cybersecurity as a risk (Exhibit 7).

Conversely, respondents are less likely than they were last year to say their organizations consider workforce and labor displacement to be relevant risks and are not increasing efforts to mitigate them.

In fact, inaccuracy— which can affect use cases across the gen AI value chain , ranging from customer journeys and summarization to coding and creative content—is the only risk that respondents are significantly more likely than last year to say their organizations are actively working to mitigate.

Some organizations have already experienced negative consequences from the use of gen AI, with 44 percent of respondents saying their organizations have experienced at least one consequence (Exhibit 8). Respondents most often report inaccuracy as a risk that has affected their organizations, followed by cybersecurity and explainability.

Our previous research has found that there are several elements of governance that can help in scaling gen AI use responsibly, yet few respondents report having these risk-related practices in place. 4 “ Implementing generative AI with speed and safety ,” McKinsey Quarterly , March 13, 2024. For example, just 18 percent say their organizations have an enterprise-wide council or board with the authority to make decisions involving responsible AI governance, and only one-third say gen AI risk awareness and risk mitigation controls are required skill sets for technical talent.

Bringing gen AI capabilities to bear

The latest survey also sought to understand how, and how quickly, organizations are deploying these new gen AI tools. We have found three archetypes for implementing gen AI solutions : takers use off-the-shelf, publicly available solutions; shapers customize those tools with proprietary data and systems; and makers develop their own foundation models from scratch. 5 “ Technology’s generational moment with generative AI: A CIO and CTO guide ,” McKinsey, July 11, 2023. Across most industries, the survey results suggest that organizations are finding off-the-shelf offerings applicable to their business needs—though many are pursuing opportunities to customize models or even develop their own (Exhibit 9). About half of reported gen AI uses within respondents’ business functions are utilizing off-the-shelf, publicly available models or tools, with little or no customization. Respondents in energy and materials, technology, and media and telecommunications are more likely to report significant customization or tuning of publicly available models or developing their own proprietary models to address specific business needs.

Respondents most often report that their organizations required one to four months from the start of a project to put gen AI into production, though the time it takes varies by business function (Exhibit 10). It also depends upon the approach for acquiring those capabilities. Not surprisingly, reported uses of highly customized or proprietary models are 1.5 times more likely than off-the-shelf, publicly available models to take five months or more to implement.

Gen AI high performers are excelling despite facing challenges

Gen AI is a new technology, and organizations are still early in the journey of pursuing its opportunities and scaling it across functions. So it’s little surprise that only a small subset of respondents (46 out of 876) report that a meaningful share of their organizations’ EBIT can be attributed to their deployment of gen AI. Still, these gen AI leaders are worth examining closely. These, after all, are the early movers, who already attribute more than 10 percent of their organizations’ EBIT to their use of gen AI. Forty-two percent of these high performers say more than 20 percent of their EBIT is attributable to their use of nongenerative, analytical AI, and they span industries and regions—though most are at organizations with less than $1 billion in annual revenue. The AI-related practices at these organizations can offer guidance to those looking to create value from gen AI adoption at their own organizations.

To start, gen AI high performers are using gen AI in more business functions—an average of three functions, while others average two. They, like other organizations, are most likely to use gen AI in marketing and sales and product or service development, but they’re much more likely than others to use gen AI solutions in risk, legal, and compliance; in strategy and corporate finance; and in supply chain and inventory management. They’re more than three times as likely as others to be using gen AI in activities ranging from processing of accounting documents and risk assessment to R&D testing and pricing and promotions. While, overall, about half of reported gen AI applications within business functions are utilizing publicly available models or tools, gen AI high performers are less likely to use those off-the-shelf options than to either implement significantly customized versions of those tools or to develop their own proprietary foundation models.

What else are these high performers doing differently? For one thing, they are paying more attention to gen-AI-related risks. Perhaps because they are further along on their journeys, they are more likely than others to say their organizations have experienced every negative consequence from gen AI we asked about, from cybersecurity and personal privacy to explainability and IP infringement. Given that, they are more likely than others to report that their organizations consider those risks, as well as regulatory compliance, environmental impacts, and political stability, to be relevant to their gen AI use, and they say they take steps to mitigate more risks than others do.

Gen AI high performers are also much more likely to say their organizations follow a set of risk-related best practices (Exhibit 11). For example, they are nearly twice as likely as others to involve the legal function and embed risk reviews early on in the development of gen AI solutions—that is, to “ shift left .” They’re also much more likely than others to employ a wide range of other best practices, from strategy-related practices to those related to scaling.

In addition to experiencing the risks of gen AI adoption, high performers have encountered other challenges that can serve as warnings to others (Exhibit 12). Seventy percent say they have experienced difficulties with data, including defining processes for data governance, developing the ability to quickly integrate data into AI models, and an insufficient amount of training data, highlighting the essential role that data play in capturing value. High performers are also more likely than others to report experiencing challenges with their operating models, such as implementing agile ways of working and effective sprint performance management.

About the research

The online survey was in the field from February 22 to March 5, 2024, and garnered responses from 1,363 participants representing the full range of regions, industries, company sizes, functional specialties, and tenures. Of those respondents, 981 said their organizations had adopted AI in at least one business function, and 878 said their organizations were regularly using gen AI in at least one function. To adjust for differences in response rates, the data are weighted by the contribution of each respondent’s nation to global GDP.

Alex Singla and Alexander Sukharevsky  are global coleaders of QuantumBlack, AI by McKinsey, and senior partners in McKinsey’s Chicago and London offices, respectively; Lareina Yee  is a senior partner in the Bay Area office, where Michael Chui , a McKinsey Global Institute partner, is a partner; and Bryce Hall  is an associate partner in the Washington, DC, office.

They wish to thank Kaitlin Noe, Larry Kanter, Mallika Jhamb, and Shinjini Srivastava for their contributions to this work.

This article was edited by Heather Hanselman, a senior editor in McKinsey’s Atlanta office.

Explore a career with us

Related articles.

Moving past gen AI’s honeymoon phase: Seven hard truths for CIOs to get from pilot to scale

A generative AI reset: Rewiring to turn potential into value in 2024

Implementing generative AI with speed and safety