Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
3.5
2.4
Journals
Mathematics
Special Issues
Graph Theoretic Concepts in Data Science
share announcement

Graph Theoretic Concepts in Data Science

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

Deadline for manuscript submissions: closed (31 July 2022) | Viewed by 7225

Special Issue Editor

Dr. Miklós Krész

E-Mail Website
Guest Editor
Andrej Marušič Institute, University of Primorska, 6000 Koper, Slovenia
Interests: algorithmic and structural graph theory; graph-based data science; diffusion models in graphs; network analysis and mining; network optimisation
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

During recent years, the mining of unstructured data has become a relevant field both in science and practical applications. Among seemingly unstructured datasets, hidden graph structures have proven to be very useful in analysis. The graph representation of these data makes it possible to use powerful methods of graph data science and also provides inspiration to develop new methods.
Network science and graph mining became the key disciplines to provide the methodology for processing and analysing of graph structured data. The powerful methods of the above fields have made it possible to discover the patterns and describe the dynamics of networked systems. On the other hand, though the classical field of graph theory ensures the modelling framework, the recent progress in discrete models and methods, such as algorithmic and structural graph theory, still has limited use in data science.
The aim of this Special Issue is to provide a forum for researchers in graph theory and data science to share their original results on the integrated use of both fields. Graph theoretic papers motivated by data science problems as well as data science applications based on graph theoretic solutions will both be considered.

Prof. Dr. Miklós Krész
Guest Editor

Manuscript Submission Information

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.

Keywords

  • data science
  • graph models
  • graph algorithms
  • network analytics
  • big data problems
  • large graphs
  • computational complexity

Published Papers (4 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Research

22 pages, 447 KiB  
Article
Clique Search in Graphs of Special Class and Job Shop Scheduling
by Sándor Szabó and Bogdán Zaválnij
Mathematics 2022, 10(5), 697; https://0-doi-org.brum.beds.ac.uk/10.3390/math10050697 - 23 Feb 2022
Cited by 4 | Viewed by 1333
Abstract
In this paper, we single out the following particular case of the clique search problem. The vertices of the given graph are legally colored with k colors and we are looking for a clique with k nodes in the graph. In other words, [...] Read more.
In this paper, we single out the following particular case of the clique search problem. The vertices of the given graph are legally colored with k colors and we are looking for a clique with k nodes in the graph. In other words, we want to decide if a given k-partite graph contains a clique with k nodes. The maximum clique problem asks for finding a maximum clique in a given finite simple graph. The problem of deciding if the given graph contains a clique with k vertices is called the k-clique problem. The first problem is NP-hard and the second one is NP-complete. The special clique search problem, we propose, is still an NP-complete problem. We will show that the k-clique problem in the special case of k-partite graphs is more tractable than in the general case. In order to illustrate the possible practical utility of this restricted type clique search problem we will show that the job shop scheduling problem can be reduced to such a clique search problem in a suitable constructed graph. We carry out numerical experiments to assess the efficiency of the approach. It is a common practice that before one embarks on a large scale clique search typically one attempts to simplify and tidy up the given graph. This procedure is commonly referred as preconditioning or kernelization of the given graph. Of course, the preconditioning or kernelization is meant with respect to the given type of clique search problem. The other main topic of the paper is to describe a number of kernelization methods tailored particularly to the proposed special k-clique problem. Some of these techniques works in connection with the generic k-clique problem. In these situations, we will see that they are more efficient in the case of k-partite graphs. Some other preconditioning methods applicable only to k-partite graphs. We illustrate how expedient these preconditioning methods can be by solving non-trivial scheduling problems to optimality employing only kernelization techniques dispensing with exhaustive clique search algorithms altogether. Full article
(This article belongs to the Special Issue Graph Theoretic Concepts in Data Science)
►▼ Show Figures

Figure 1

21 pages, 348 KiB  
Article
Resolvable Networks—A Graphical Tool for Representing and Solving SAT
by Gábor Kusper, Csaba Biró and Benedek Nagy
Mathematics 2021, 9(20), 2597; https://0-doi-org.brum.beds.ac.uk/10.3390/math9202597 - 15 Oct 2021
Cited by 1 | Viewed by 1161
Abstract
In this paper, we introduce the notion of resolvable networks. A resolvable network is a digraph of subnetworks, where subnetworks may overlap, and the inner structure of subnetworks are not interesting from the viewpoint of the network. There are two special subnetworks, Source [...] Read more.
In this paper, we introduce the notion of resolvable networks. A resolvable network is a digraph of subnetworks, where subnetworks may overlap, and the inner structure of subnetworks are not interesting from the viewpoint of the network. There are two special subnetworks, Source and Sink, with the following properties: there is no incoming edge to Source, and there is no outgoing edge from Sink. Any resolvable network can be represented by a satisfiability problem in Boolean logic (shortly, SAT problem), and any SAT problem can be represented by a resolvable network. Because of that, the resolution operation is valid also for resolvable networks. We can use resolution to find out or refine the inner structure of subnetworks. We give also a pessimistic and an optimistic interpretation of subnetworks. In the pessimistic case, we assume that inside a subnetwork, all communication possibilities are represented as part of the resolvable network. In the optimistic case, we assume that each subnetwork is strongly connected. We show that any SAT problem can be visualized using the pessimistic interpretation. We show that transitivity is very limited in the pessimistic interpretation, and in this case, transitivity corresponds to resolution of clauses. In the optimistic interpretation of subnetworks, we have transitivity without any further condition, but not all SAT problems can be represented in this case; however, any such network can be represented as a SAT problem. The newly introduced graphical concept allows to use terminology and tools from directed graphs in the field of SAT and also to give graphical representations of various concepts of satisfiability problems. A resolvable network is also a suitable data structure to study, for example, wireless sensor networks. The visualization power of resolvable networks is demonstrated on some pigeon hole SAT problems. Another important application field could be modeling the communication network of an information bank. Here, a subnetwork represents a dataset of a user which is secured by a proxy. Any communication should be done through the proxy, and this constraint can be checked using our model. Full article
(This article belongs to the Special Issue Graph Theoretic Concepts in Data Science)
►▼ Show Figures

Figure 1

24 pages, 4306 KiB  
Article
A Novel Analytic Framework of Technology Mining Using the Main Path Analysis and the Decision-Making Trial and Evaluation Laboratory-Based Analytic Network Process
by Chi-Yo Huang, Liang-Chieh Wang, Ying-Ting Kuo and Wei-Ti Huang
Mathematics 2021, 9(19), 2448; https://0-doi-org.brum.beds.ac.uk/10.3390/math9192448 - 02 Oct 2021
Cited by 3 | Viewed by 1635
Abstract
Tech mining is an analytical method of technology monitoring that can reveal technology trends in different industries. Patent databases are the major sources for information retrieval by tech mining methods. The majority of the commercially viable research and development results in the world [...] Read more.
Tech mining is an analytical method of technology monitoring that can reveal technology trends in different industries. Patent databases are the major sources for information retrieval by tech mining methods. The majority of the commercially viable research and development results in the world can be found in patents. The time and cost of research and development can greatly be reduced if researchers properly analyze patents of prior arts. Appropriate analyses of patents also help firms avoid patent infringement while simultaneously developing new products or services. The main path analysis is a bibliometric method which can be used to derive the most dominant paths in a citation network of patents or academic works and has widely been adopted in tracing the development trajectory of a specific science or technology. Even though main path analysis can derive patent citation relationships and the weight associated with some specific arc of the citation network, the weights associated with patents and influence relationships among patents can hardly be derived based on methods of main path analysis. However, these influence relationships and weight can be crucial for defining research and development and patent aggregation strategies. Thus, the authors want to propose a novel analytic framework which consists of the Decision-Making Trial and Evaluation Laboratory (DEMATEL), the DEMATEL based Analytic Network Process (DANP) and the main path analysis. The proposed analytic framework can be used to derive the influence relationships and influence weights associated with the patents in a main path. Empirical cases based on the main path of a published work and the patent mining results of nanowire field effect transistors from the database of the United States Patent and Trademark Office will be used to demonstrate the feasibility of the proposed analytic framework. The analytic results of empirical research can be used as a basis for infringement evaluation, patent designing around and innovation. Full article
(This article belongs to the Special Issue Graph Theoretic Concepts in Data Science)
►▼ Show Figures

Figure 1

14 pages, 16787 KiB  
Article
Adaptation of Random Binomial Graphs for Testing Network Flow Problems Algorithms
by Adrian Marius Deaconu and Delia Spridon
Mathematics 2021, 9(15), 1716; https://0-doi-org.brum.beds.ac.uk/10.3390/math9151716 - 21 Jul 2021
Cited by 2 | Viewed by 1744
Abstract
Algorithms for network flow problems, such as maximum flow, minimum cost flow, and multi-commodity flow problems, are continuously developed and improved, and so, random network generators become indispensable to simulate the functionality and to test the correctness and the execution speed of these [...] Read more.
Algorithms for network flow problems, such as maximum flow, minimum cost flow, and multi-commodity flow problems, are continuously developed and improved, and so, random network generators become indispensable to simulate the functionality and to test the correctness and the execution speed of these algorithms. For this purpose, in this paper, the well-known Erdős–Rényi model is adapted to generate random flow (transportation) networks. The developed algorithm is fast and based on the natural property of the flow that can be decomposed into directed elementary s-t paths and cycles. So, the proposed algorithm can be used to quickly build a vast number of networks as well as large-scale networks especially designed for s-t flows. Full article
(This article belongs to the Special Issue Graph Theoretic Concepts in Data Science)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-4
Back to TopTop