Narrow Results

The new definition of a fuzzy vertex cover of a fuzzy graph depending on the fuzzy covering radius is introduced in this paper. A fuzzy covering problem for a fuzzy network in modification of the fuzzy covering radius as per requirement is considered and solved in an optimization sense. The covering problem is customized with the help of a set of programming problems, and they are solved by using mathematical software “LINGO”. Two relevant algorithms are designed in this paper. Also, one of the burning issues of today’s world, “Climate Action” (one of the most important sustainable developmental goals), together with various weather parameters, is taken in the application part. The fuzzy environment for this issue of India to save our nature is modeled for making some decisions to improve the situations for this purpose, and the whole methodology reflects the importance of the applicability of our proposed model.

Numerous graph-theoretic methods can be used to investigate the efficiency and reliability of networks. The reliability of a network is determined based on its connectivity. At the very least, the system must continue to function in the event of part of its component (node or link) failures. An ideal system remains reliable even when errors occur. Diameter is a measure of network efficiency used to study the effects of link failures in networks. In this paper, we look into the eliminating edges affect to the hypercube graph’s diameter (call it by $d$) and calculate the maximum diameter that is denoted by $f(t,d)$ after deleting $t$ edges from hypercube graphs $Q_n$ for some n.

In a cooperation with the national German railway company, we construct a directed graph from a set of train time tables where train stations correspond to vertices, and where pairs of consecutive stops of trains correspond to edges. We consider the problem of locating vertices of this time table graph that intuitively correspond to train stations where the underlying railroad network branches into several directions, and that induce a partition of the edge set into bundles.

We formulate this problem as a graph theoretic optimization problem, and show for two versions of the problem that they are NP-hard. For the first version we show that it is even NP-complete to decide whether any other solution besides the trival one exists.

The rupture degree of a graph is a measure of the vulnerability of a graph. In this paper we investigate a refinement that involves the weak version of the parameter. The weak-rupture degree of a connected graph G is defined to be $R_{\omega }\left(G\right)=\max \left\{\omega \left(G-S\right)-\left|S\right|-m_e\left(G-S\right):S\subseteq V\left(G\right),\omega \left(G-S\right)>1\right\}$ where $\omega \left(G-S\right)$ is the number of the components of $\left(G-S\right)$ and $m_e\left(G-S\right)$ is the number of edges of the largest component of $G-S$. Like the rupture degree itself, this is a measure of the vulnerability of a graph, but it is more sensitive. This paper, the weak-rupture degree of some special graphs are obtained and some bounds of the weak-rupture degree are given. Moreover some results about the weak-rupture degree of graphs obtained by graph operations are given.

Link residual closeness is reported as a new graph vulnerability measure, a graph-based approach to network vulnerability analysis, and more sensitive than some other existing vulnerability measures. Residual closeness is of great theoretical and practical significance to network design and optimization. In this paper, how some of the graph types perform when they suffer a link failure is discussed. Vulnerability of graphs to the failure of individual links is computed via link residual closeness which provides a much fuller characterization of the network.

Let $G$ be a graph and $S\subseteq V(G)$. We define by $〈S〉$ the subgraph of $G$ induced by $S$. For each vertex $u\in S$ and for each vertex $v\in S\setminus \{u\}$, $d_{(G,S\setminus \{u\})}(u,v)$ is the length of the shortest path in $〈V(G)-((S-\{u\})-\{v\})〉$ between $u$ and $v$ if such a path exists, and $\infty$ otherwise. For a vertex $u\in S$, let ${\omega }_{(G,S\setminus \{u\})}(u)={\sum }_{v\in S\setminus \{u\}}{(\frac{1}{2})}^{d_{(G,S\setminus \{u\})}(u,v)-1}$ where $\left(\right.\frac{1}{2}{\left)\right.}^{\infty }=0$. Jäger and Rautenbach [27] define a set $S$ of vertices to be exponential independent if ${\omega }_{(G,S\setminus \{u\})}(u)<1$ for every vertex $u$ in $S$. The exponential independence number ${\alpha }_e(G)$ of $G$ is the maximum order of an exponential independent set. In this paper, we give a general theorem and we examine exponential independence number of some tree graphs and thorn graph of some graphs.

Graph data structure has been widely used across many application areas, such as web data, social network, and cheminformatics. The main benefit of storing data as graphs is there exists a rich set of graph algorithms and operations that can be used to solve various computing problems, including pattern matching, data mining, and image processing. Among these graph algorithms, the subgraph isomorphism problem is one of the most fundamental algorithms that can be utilized by many higher level applications. The subgraph isomorphism problem is defined as, given two graphs $G$ and $H$, whether $G$ contains a subgraph that is isomorphic to $H$. In this paper, we consider a special case of the subgraph isomorphism problem called the subgraph matching problem, which tests whether $G$ is a subgraph of $H$. We propose a protocol that solve the subgraph matching problem in a privacy-preserving manner. The protocol allows two parties to jointly compute whether one graph is a subgraph of the other, while protecting the private information about the input graphs. The protocol is secure under the semi-honest setting, where each party performs the protocol faithfully.

Link residual closeness is a novel graph based network vulnerability parameter. In this model, nodes are perfectly reliable and the links fail independently of each other. In this paper, the behavior of composite network types to the failure of individual links are observed and analyzed via link residual closeness which provides a much fuller characterization of the network.

A nonempty set C of vertices of a graph G is a star-cutset if G\C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. A graph G is unbreakable if neither G nor its complement Ḡ contains a star-cutset. In this note we present a new characterization of unbreakable graphs.

It is increasingly being recognized that resting state brain connectivity derived from functional magnetic resonance imaging (fMRI) data is an important marker of brain function both in healthy and clinical populations. Though linear correlation has been extensively used to characterize brain connectivity, it is limited to detecting first order dependencies. In this study, we propose a framework where in phase synchronization (PS) between brain regions is characterized using a new metric "correlation between probabilities of recurrence" (CPR) and subsequent graph-theoretic analysis of the ensuing networks. We applied this method to resting state fMRI data obtained from human subjects with and without administration of propofol anesthetic. Our results showed decreased PS during anesthesia and a biologically more plausible community structure using CPR rather than linear correlation. We conclude that CPR provides an attractive nonparametric method for modeling interactions in brain networks as compared to standard correlation for obtaining physiologically meaningful insights about brain function.

The aim of this study was to introduce a novel global measure of graph complexity: Shannon graph complexity (SGC). This measure was specifically developed for weighted graphs, but it can also be applied to binary graphs. The proposed complexity measure was designed to capture the interplay between two properties of a system: the ‘information’ (calculated by means of Shannon entropy) and the ‘order’ of the system (estimated by means of a disequilibrium measure). SGC is based on the concept that complex graphs should maintain an equilibrium between the aforementioned two properties, which can be measured by means of the edge weight distribution. In this study, SGC was assessed using four synthetic graph datasets and a real dataset, formed by electroencephalographic (EEG) recordings from controls and schizophrenia patients. SGC was compared with graph density (GD), a classical measure used to evaluate graph complexity. Our results showed that SGC is invariant with respect to GD and independent of node degree distribution. Furthermore, its variation with graph size $(N)$ is close to zero for $N>30$. Results from the real dataset showed an increment in the weight distribution balance during the cognitive processing for both controls and schizophrenia patients, although these changes are more relevant for controls. Our findings revealed that SGC does not need a comparison with null-hypothesis networks constructed by a surrogate process. In addition, SGC results on the real dataset suggest that schizophrenia is associated with a deficit in the brain dynamic reorganization related to secondary pathways of the brain network.

Motor imagery (MI) requires subjects to visualize the requested motor behaviors, which involves a large-scale network that spans multiple brain areas. The corresponding cortical activity reflected on the scalp is characterized by event-related desynchronization (ERD) and then by event-related synchronization (ERS). However, the network mechanisms that account for the dynamic information processing of MI during the ERD and ERS periods remain unknown. Here, we combined ERD/ERS analysis with the dynamic networks in different MI stages (i.e. motor preparation, ERD and ERS) to probe the dynamic processing of MI information. Our results show that specific dynamic network structures correspond to the ERD/ERS evolution patterns. Specifically, ERD mainly shows the contralateral networks, while ERS has the symmetric networks. Moreover, different dynamic network patterns are also revealed between the two types of MIs, in which the left-hand MIs exhibit a relatively less sustained contralateral network, which may be the network mechanism that accounts for the bilateral ERD/ERS observed for the left-hand MIs. Similar to the network topologies, the three MI stages also appear to be characterized by different network properties. The above findings all demonstrate that different MI stages that involve specific brain networks for dynamically processing the MI information.

Aim of this study was to explore the EEG functional connectivity in amnesic mild cognitive impairments (MCI) subjects with multidomain impairment in order to characterize the Default Mode Network (DMN) in converted MCI (cMCI), which converted to Alzheimer’s disease (AD), compared to stable MCI (sMCI) subjects. A total of 59 MCI subjects were recruited and divided -after appropriate follow-up- into cMCI or sMCI. They were further divided in MCI with linguistic domain (LD) impairment and in MCI with executive domain (ED) impairment. Small World (SW) index was measured as index of balance between integration and segregation brain processes. SW, computed restricting to nodes of DMN regions for all frequency bands, evaluated how they differ between MCI subgroups assessed through clinical and neuropsychological four-years follow-up. In addition, SW evaluated how this pattern differs between MCI with LD and MCI with ED. Results showed that SW index significantly decreased in gamma band in cMCI compared to sMCI. In cMCI with LD impairment, the SW index significantly decreased in delta band, while in cMCI with ED impairment the SW index decreased in delta and gamma bands and increased in alpha1 band. We propose that the DMN functional alterations in cognitive impairment could reflect an abnormal flow of brain information processing during resting state possibly associated to a status of pre-dementia.

The objective of this work was to study the impact of repetitive Transcranial Magnetic Stimulation (rTMS) on the EEG connectivity evaluated by indices based on graph theory, derived from Directed Transfer Function (DTF), in patients with major depressive disorder (MDD) or with bipolar disorder (BD). The results showed the importance of beta and gamma rhythms. The indices density, degree and clustering coefficient increased in MDD responders in beta and gamma bands after rTMS. Interestingly, the density and the degree changed in theta band in both groups of nonresponders (decreased in MDD nonresponders but increased in BD nonresponders). Moreover, both indices of integration (the characteristic path length and the global efficiency) as well as the clustering coefficient increased in BD nonresponders for gamma band. In BD responders, the activity increased in the frontal lobe, mainly in the left hemisphere, while in MDD responders in the central posterior part of brain. The fronto-posterior asymmetry decreased in both groups of responders in delta and beta bands. Changes in inter-hemispheric asymmetry were found only in BD nonresponders in all bands, except gamma band. Comparison between groups showed that the degree increased in delta band independently on disease (BD, MDD). These preliminary results showed that the DTF may be a useful marker allowing for evaluation of effectiveness of the rTMS therapy as well for group differentiation between MDD and BD considering separately groups of responders and nonresponders. However, further investigation should be performed over larger groups of patients to confirmed our findings.

Among the several findings deriving from the application of complex network formalism to the investigation of natural phenomena, the fact that linguistic constructions follow power laws presents special interest for its potential implications for psychology and brain science. By corresponding to one of the most essentially human manifestations, such language-related properties suggest that similar dynamics may also be inherent to the brain areas related to language and associative memory, and perhaps even consciousness. The present work reports a preliminary experimental investigation aimed at characterizing and modeling the flow of sequentially induced associations between words from the English language in terms of complex networks. The data is produced through a psychophysical experiment where a word is presented to the subject, who is requested to associate another word. Complex network and graph theory formalism and measurements are applied in order to characterize the experimental data. Several interesting results are identified, including the characterization of attraction basins, association asymmetries, context biasing, as well as a possible power-law underlying word associations, which could be explained by the appearance of strange loops along the hierarchical structure underlying word categories.

A family of graphs optimized as the topologies for interconnection networks is proposed. The needs of such topologies with minimal diameters and minimal mean path lengths are met by special constructions of the weight vectors in a representation of the symplectic algebra. Such design of topologies can conveniently reconstruct the mesh and hypercube, widely used as network topologies, as well as many other classes of graphs potentially suitable for network topologies.

Link residual closeness (LRC) is a new sensitive characteristic for network vulnerability analysis. LRC measures the vulnerability even when the removal of links does not disconnect the network. In this paper, the robustness of wheel type network topologies is modeled and analyzed via LRC in the face of possible link destruction.

A new program created in C/C$++$ language generates automatically the analytic expression of grand potential and prints it in Latex2e format and in textual data. Another code created in Mathematica language can translate the textual data into a mathematical expression and help any interested to evaluate the thermodynamic quantities in analytic or numeric forms.

Graph algorithms are becoming increasingly important for solving many problems in scientific computing, data mining and other domains. As these problems grow in scale, parallel computing resources are required to meet their computational and memory requirements. Unfortunately, the algorithms, software, and hardware that have worked well for developing mainstream parallel scientific applications are not necessarily effective for large-scale graph problems. In this paper we present the inter-relationships between graph problems, software, and parallel hardware in the current state of the art and discuss how those issues present inherent challenges in solving large-scale graph problems. The range of these challenges suggests a research agenda for the development of scalable high-performance software for graph problems.

In previous papers, we have developed the theoretical background for the design of deadlock-free adaptive routing algorithms for store-and-forward and wormhole networks. Some definitions and theorems have been proposed, developing conditions to verify that an adaptive algorithm is deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies have been proposed.

In this paper, we propose a partial order between channels as well as an equivalence relation. This relation splits the set of channels into equivalence classes. Then, we extend our previous theory by considering equivalence classes (channel classes) instead of channels. This extension drastically simplifies the verification of deadlock freedom for adaptive routing algorithms with cyclic dependencies between channels. Finally, we present an example.