Submit to Mathematics Review for Mathematics Propose a Special Issue

Journal Browser

New Trends in Graph and Complexity Based Data Analysis and Processing

Print Special Issue Flyer
Special Issue Editors
Special Issue Information
Keywords
Published Papers

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

Deadline for manuscript submissions: closed (20 May 2022) | Viewed by 25973

Share This Special Issue

Special Issue Editors

Prof. Dr. Jonatan Lerga

E-Mail Website
Guest Editor

1. Faculty of Engineering, University of Rijeka, Vukovarska 58, 51000 Rijeka, Croatia
2. Center for Artificial Intelligence and Cybersecurity, Radmile Matejcic 2, 51000 Rijeka, Croatia
Interests: signal processing; time-frequency signal analysis; information theory; coding; image and video processing
Special Issues, Collections and Topics in MDPI journals

Prof. Dr. Ljubisa Stankovic

E-Mail Website
Guest Editor

Faculty of Electrical Engineering, University of Montenegro, Dzordžz Vasingtona bb, 81000 Podgorica, Montenegro
Interests: digital signal processing; time-frequency signal analysis; compressive sensing; graph signal processing; radar signal processing
Special Issues, Collections and Topics in MDPI journals

Dr. Nicoletta Saulig

E-Mail Website
Guest Editor

Department of Engineering, Juraj Dobrila University of Pula, Pula, Croatia
Interests: digital signal processing; time-frequency analysis
Special Issues, Collections and Topics in MDPI journals

Dr. Cornel Ioana

E-Mail Website
Guest Editor

Gipsa-Lab, Universite Grenoble Alpes, Saint Martin d'Heres, 38400 Grenoble, France
Interests: compressed sensing; signal reconstruction; time-frequency analysis; Fourier transforms; bathymetry; signal representation; sonar imaging; acoustic imaging; acoustic signal processing; acoustic wave interferometers; array signal processing; frequency modulation; measurement uncertainty; oceanographic techniques; polynomials; quantisation (signal); signal resolution; sonar detection; sonar signal processing; underwater sound; doppler shift; Gaussian processes; acoustic measurement; acoustic noise; angular measurement
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

Analysis and processing of data may significantly benefit from an appropriate relation of the sensing points, signal values, or analyzed objects. In this way, a new data domain in the form of a graph arises and naturally and comprehensively takes into account irregular data relations in the problem definition, together with the corresponding data connectivity. The introduction of new graph-based relations between the time-series samples, in well-defined time and space domains, may also lead to new insights into signal analysis and provide enhanced data processing. Although graph theory, as a branch of mathematics, was established a long time ago, it has been largely focused on analyzing the underlying graphs rather than signals and data on graphs, which turn out to be a hot recent research topic.

In addition, in recent years, classical complexity and entropy measures have been upgraded by new entropy-like measures focusing on multidimensional generalizations of the concepts with special attention directed to the quantification of similarity and coupling between time series and system components behind them. Recent research is focused on understanding the nature of complexity measures, their relationships, and proper parameter selection for various real-life applications.

Prof. Dr. Jonatan Lerga
Prof. Dr. Ljubisa Stankovic
Prof. Dr. Nicoletta Saulig
Prof. Dr. Cornel Ioana
Guest Editors

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

Graph and graph-based data classification and clustering
Graph neural networks
Graph topology learning from data
Dynamic graph structures
Vertex–frequency and wavelet analysis of signals on graphs
Graph complexity and the complexity of signals on graphs
Entropy and entropy-like measures
Complexity measures
Classical signal and image processing assisted by graph theory
Graph filtering and adaptive processing
Interpolation, subsampling and downscaling of graph signals and graphs
Applications of graph data processing
Applications of entropy and complexity based measures

Published Papers (10 papers)

Download All Papers

Research

16 pages, 1611 KiB

Open AccessArticle

Relational Structure-Aware Knowledge Graph Representation in Complex Space

by Ke Sun, Shuo Yu, Ciyuan Peng, Yueru Wang, Osama Alfarraj, Amr Tolba and Feng Xia

Mathematics 2022, 10(11), 1930; https://0-doi-org.brum.beds.ac.uk/10.3390/math10111930 - 04 Jun 2022

Cited by 2 | Viewed by 2353

Abstract

Relations in knowledge graphs have rich relational structures and various binary relational patterns. Various relation modelling strategies are proposed for embedding knowledge graphs, but they fail to fully capture both features of relations, rich relational structures and various binary relational patterns. To address the problem of insufficient embedding due to the complexity of the relations, we propose a novel knowledge graph representation model in complex space, namely MARS, to exploit complex relations to embed knowledge graphs. MARS takes the mechanisms of complex numbers and message-passing and then embeds triplets into relation-specific complex hyperplanes. Thus, MARS can well preserve various relation patterns, as well as structural information in knowledge graphs. In addition, we find that the scores generated from the score function approximate a Gaussian distribution. The scores in the tail cannot effectively represent triplets. To address this particular issue and improve the precision of embeddings, we use the standard deviation to limit the dispersion of the score distribution, resulting in more accurate embeddings of triplets. Comprehensive experiments on multiple benchmarks demonstrate that our model significantly outperforms existing state-of-the-art models for link prediction and triple classification. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

17 pages, 1246 KiB

Open AccessArticle

Multicriteria Optimization Problem on Prefractal Graph

by Rasul Kochkarov

Mathematics 2022, 10(6), 930; https://0-doi-org.brum.beds.ac.uk/10.3390/math10060930 - 14 Mar 2022

Cited by 3 | Viewed by 1442

Abstract

Even among single-criteria discrete problems, there are NP-hard ones. Multicriteria problems on graphs in many cases become intractable. Currently, priority is given to the study of applied multicriteria problems with specific criteria; there is no classification of criteria according to their type and content. There are few studies with fuzzy criteria, both weight and topological. Little attention is paid to the stability of solutions, and this is necessary when modeling real processes due to their dynamism. It is also necessary to study the behavior of solution sets for various general and individual problems. The theory of multicriteria optimization is a rather young branch of science and requires the development of not only particular methods, but also the construction of a methodological basis. This is also true in terms of discrete graph-theoretic optimization. In this paper, we propose to get acquainted with multicriteria problems for a special class of prefractal graphs. Modeling natural objects or processes using graphs often involves weighting edges with many numbers. The author proposes a general formulation of a multicriteria problem on a multi-weighted prefractal graph; defines three sets of alternatives—Pareto, complete and lexicographic; and proposes a classification of individual problems according to the set of feasible solutions. As an example, we consider an individual problem of placing a multiple center with two types of weight criteria and two types of topological ones. An algorithm with estimates of all criteria of the problem is proposed. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

16 pages, 21701 KiB

Open AccessArticle

Semi-Local Integration Measure of Node Importance

by Tajana Ban Kirigin, Sanda Bujačić Babić and Benedikt Perak

Mathematics 2022, 10(3), 405; https://0-doi-org.brum.beds.ac.uk/10.3390/math10030405 - 27 Jan 2022

Cited by 4 | Viewed by 2710

Abstract

Numerous centrality measures have been introduced as tools to determine the importance of nodes in complex networks, reflecting various network properties, including connectivity, survivability, and robustness. In this paper, we introduce Semi-Local Integration (

S L I

), a node centrality measure for [...] Read more.

S L I

), a node centrality measure for undirected and weighted graphs that takes into account the coherence of the locally connected subnetwork and evaluates the integration of nodes within their neighbourhood. We illustrate

S L I

node importance differentiation among nodes in lexical networks and demonstrate its potential in natural language processing (NLP). In the NLP task of sense identification and sense structure analysis, the

S L I

centrality measure evaluates node integration and provides the necessary local resolution by differentiating the importance of nodes to a greater extent than standard centrality measures. This provides the relevant topological information about different subnetworks based on relatively local information, revealing the more complex sense structure. In addition, we show how the

S L I

measure can improve the results of sentiment analysis. The

S L I

measure has the potential to be used in various types of complex networks in different research areas. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

20 pages, 2458 KiB

Open AccessArticle

Research of NP-Complete Problems in the Class of Prefractal Graphs

by Rasul Kochkarov

Mathematics 2021, 9(21), 2764; https://0-doi-org.brum.beds.ac.uk/10.3390/math9212764 - 31 Oct 2021

Cited by 6 | Viewed by 2824

Abstract

NP-complete problems in graphs, such as enumeration and the selection of subgraphs with given characteristics, become especially relevant for large graphs and networks. Herein, particular statements with constraints are proposed to solve such problems, and subclasses of graphs are distinguished. We propose a class of prefractal graphs and review particular statements of NP-complete problems. As an example, algorithms for searching for spanning trees and packing bipartite graphs are proposed. The developed algorithms are polynomial and based on well-known algorithms and are used in the form of procedures. We propose to use the class of prefractal graphs as a tool for studying NP-complete problems and identifying conditions for their solvability. Using prefractal graphs for the modeling of large graphs and networks, it is possible to obtain approximate solutions, and some exact solutions, for problems on natural objects—social networks, transport networks, etc. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

22 pages, 794 KiB

Open AccessArticle

Lexical Sense Labeling and Sentiment Potential Analysis Using Corpus-Based Dependency Graph

by Tajana Ban Kirigin, Sanda Bujačić Babić and Benedikt Perak

Mathematics 2021, 9(12), 1449; https://0-doi-org.brum.beds.ac.uk/10.3390/math9121449 - 21 Jun 2021

Cited by 5 | Viewed by 3607

Abstract

This paper describes a graph method for labeling word senses and identifying lexical sentiment potential by integrating the corpus-based syntactic-semantic dependency graph layer, lexical semantic and sentiment dictionaries. The method, implemented as ConGraCNet application on different languages and corpora, projects a semantic function onto a particular syntactical dependency layer and constructs a seed lexeme graph with collocates of high conceptual similarity. The seed lexeme graph is clustered into subgraphs that reveal the polysemous semantic nature of a lexeme in a corpus. The construction of the WordNet hypernym graph provides a set of synset labels that generalize the senses for each lexical cluster. By integrating sentiment dictionaries, we introduce graph propagation methods for sentiment analysis. Original dictionary sentiment values are integrated into ConGraCNet lexical graph to compute sentiment values of node lexemes and lexical clusters, and identify the sentiment potential of lexemes with respect to a corpus. The method can be used to resolve sparseness of sentiment dictionaries and enrich the sentiment evaluation of lexical structures in sentiment dictionaries by revealing the relative sentiment potential of polysemous lexemes with respect to a specific corpus. The proposed approach has the potential to be used as a complementary method to other NLP resources and tasks, including word disambiguation, domain relatedness, sense structure, metaphoricity, as well as a cross- and intra-cultural discourse variations of prototypical conceptualization patterns and knowledge representations. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Graphical abstract

14 pages, 3633 KiB

Open AccessArticle

Entropy-Based Characterization of the Transient Phenomena—Systemic Approach

by Denis Stanescu, Angela Digulescu, Cornel Ioana and Alexandru Serbanescu

Mathematics 2021, 9(6), 648; https://0-doi-org.brum.beds.ac.uk/10.3390/math9060648 - 18 Mar 2021

Cited by 5 | Viewed by 2151

Abstract

The difficulties of predictive maintenance of power grids are related to the large spread of electrical infrastructures and the definition of early warning indicators. Such indicator is the partial discharge activities—which can be very informative about the rising insulation problems of electrical materials. However, the detection and the localization of the partial discharges are very complicate tasks and are currently subject to intensive studies in both theoretical and practical domains. The traditional way to approach the global surveillance of partial discharge sources is to first detect it and the second is to attempt to localize their positions. Despite the numerous proposed approaches, based on advanced transient signal processing tools, there is no any operational technique to efficiently asses the partial discharge sources in a real power network. In this context, our paper proposes a new approach based on the global evaluation of entropy of transient phenomena detected in a power network, without needing any localization of the sources of these phenomena. We will show that this approach provides an effective evaluation of partial discharges sources. Moreover, since the technique requires a reduced number of sensors, it is very advantageous to use in real contexts. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

27 pages, 2617 KiB

Open AccessArticle

Rule-Based EEG Classifier Utilizing Local Entropy of Time–Frequency Distributions

by Jonatan Lerga, Nicoletta Saulig, Ljubiša Stanković and Damir Seršić

Mathematics 2021, 9(4), 451; https://0-doi-org.brum.beds.ac.uk/10.3390/math9040451 - 23 Feb 2021

Cited by 7 | Viewed by 2399

Abstract

Electroencephalogram (EEG) signals are known to contain signatures of stimuli that induce brain activities. However, detecting these signatures to classify captured EEG waveforms is one of the most challenging tasks of EEG analysis. This paper proposes a novel time–frequency-based method for EEG analysis and characterization implemented in a computer-aided decision-support system that can be used to assist medical experts in interpreting EEG patterns. The computerized method utilizes EEG spectral non-stationarity, which is clearly revealed in the time–frequency distributions (TFDs) of multicomponent signals. The proposed algorithm, which is based on the modification of the Rényi entropy, called local or short-term Rényi entropy (STRE), was upgraded with a blind component separation procedure and instantaneous frequency (IF) estimation. The method was applied to EEGs of both forward and backward movements of the left and right hands, as well as to EEGs of imagined hand movements, which were captured by a 19-channel EEG recording system. The obtained results show that in a given virtual instrument, the proposed methods efficiently distinguish between real and imagined limb movements by considering their signatures in terms of the dominant EEG component’s IFs at the specified subset of EEG channels (namely, F3, F4, F7, F8, T3, and T4). Furthermore, computing the number of EEG signal components, their extraction, and IF estimation provide important information that shows potential to enhance existing clinical diagnostic techniques for detecting the intensity, location, and type of brain function abnormalities in patients with neurological motor control disorders. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

18 pages, 7362 KiB

Open AccessFeature PaperArticle

ConvGraph: Community Detection of Homogeneous Relationships in Weighted Graphs

by Héctor Muñoz, Eloy Vicente, Ignacio González, Alfonso Mateos and Antonio Jiménez-Martín

Mathematics 2021, 9(4), 367; https://0-doi-org.brum.beds.ac.uk/10.3390/math9040367 - 12 Feb 2021

Cited by 2 | Viewed by 2244

Abstract

This paper proposes a new method, ConvGraph, to detect communities in highly cohesive and isolated weighted graphs, where the sum of the weights is significantly higher inside than outside the communities. The method starts by transforming the original graph into a line graph to apply a convolution, a common technique in the computer vision field. Although this technique was originally conceived to detect the optimum edge in images, it is used here to detect the optimum edges in communities identified by their weights rather than by their topology. The method includes a final refinement step applied to communities with a high vertex density that could not be detected in the first phase. The proposed algorithm was tested on a series of highly cohesive and isolated synthetic graphs and on a real-world export graph, performing well in both cases. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

18 pages, 486 KiB

Open AccessArticle

Double Roman Graphs in P(3k, k)

by Zehui Shao, Rija Erveš, Huiqin Jiang, Aljoša Peperko, Pu Wu and Janez Žerovnik

Mathematics 2021, 9(4), 336; https://0-doi-org.brum.beds.ac.uk/10.3390/math9040336 - 08 Feb 2021

Cited by 5 | Viewed by 1831

Abstract

A double Roman dominating function on a graph

G = (V, E)

is a function

f : V \to {0, 1, 2, 3}

with the properties that if

f (u) = 0

, [...] Read more.

A double Roman dominating function on a graph

G = (V, E)

is a function

f : V \to {0, 1, 2, 3}

with the properties that if

f (u) = 0

, then vertex u is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if

f (u) = 1

, then vertex u is adjacent to at least one vertex assigned 2 or 3. The weight of f equals

w (f) = \sum_{v \in V} f (v)

. The double Roman domination number

γ_{d R} (G)

of a graph G is the minimum weight of a double Roman dominating function of G. A graph is said to be double Roman if

γ_{d R} (G) = 3 γ (G)

, where

γ (G)

is the domination number of G. We obtain the sharp lower bound of the double Roman domination number of generalized Petersen graphs

P (3 k, k)

, and we construct solutions providing the upper bounds, which gives exact values of the double Roman domination number for all generalized Petersen graphs

P (3 k, k)

. This implies that

P (3 k, k)

is a double Roman graph if and only if either

k \equiv 0

(mod 3) or

k \in {1, 4}

. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

33 pages, 2851 KiB

Open AccessArticle

A Signal Complexity-Based Approach for AM–FM Signal Modes Counting

by Vittoria Bruni, Michela Tartaglione and Domenico Vitulano

Mathematics 2020, 8(12), 2170; https://0-doi-org.brum.beds.ac.uk/10.3390/math8122170 - 04 Dec 2020

Cited by 10 | Viewed by 1868

Abstract

Frequency modulated signals appear in many applied disciplines, including geology, communication, biology and acoustics. They are naturally multicomponent, i.e., they consist of multiple waveforms, with specific time-dependent frequency (instantaneous frequency). In most practical applications, the number of modes—which is unknown—is needed for correctly analyzing a signal; for instance for separating each individual component and for estimating its instantaneous frequency. Detecting the number of components is a challenging problem, especially in the case of interfering modes. The Rényi Entropy-based approach has proven to be suitable for signal modes counting, but it is limited to well separated components. This paper addresses this issue by introducing a new notion of signal complexity. Specifically, the spectrogram of a multicomponent signal is seen as a non-stationary process where interference alternates with non-interference. Complexity concerning the transition between consecutive spectrogram sections is evaluated by means of a modified Run Length Encoding. Based on a spectrogram time-frequency evolution law, complexity variations are studied for accurately estimating the number of components. The presented method is suitable for multicomponent signals with non-separable modes, as well as time-varying amplitudes, showing robustness to noise. Full article

(This article belongs to the Special Issue New Trends in Graph and Complexity Based Data Analysis and Processing)

► Show Figures

Figure 1

Journal Menu

Journal Browser

New Trends in Graph and Complexity Based Data Analysis and Processing

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Published Papers (10 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI