Search

In this paper, we present a general framework to estimate the network entropy that is represented by means of an undirected graph and subsequently employ this framework for graph classification tasks. The proposed framework is based on local information functionals which are defined using induced connected subgraphs of different sizes. These induced subgraphs are termed graphlets. Specifically, we extract the set of all graphlets of a specific sizes and compute the graph entropy using our proposed framework. To classify the network into different categories, we construct a feature vector whose components are obtained by computing entropies of different graphlet sizes. We apply the proposed framework to two different tasks, namely view-based object recognition and biomedical datasets with binary outcomes classification. Finally, we report and compare the classification accuracies of the proposed method and compare against some of the state-of-the-art methods.

Motivated by the concept of Shannon’s entropy, the degree-dependent weighted graph entropy was defined which is now become a tool for measurement of structural information of complex graph networks. The aim of this paper is to study weighted graph entropy. We used GA and Gaurava indices as edge weights to define weighted graph entropy and establish some bounds for different families of graphs. Moreover, we compute the defined weighted entropies for molecular graphs of some dendrimer structures.

Topological indices as a molecular descriptors are important tools in ( QSAR ) / ( QSPR ) studies. The graph entropies with topological indices inspired by Shannon’s entropy concept become the information-theoretic quantities for measuring the structural information of chemical graphs and complex networks. The graph entropy measures are playing an important role in a variety of problem areas including, discrete mathematics, biology, and chemistry. Our contribution is to explore graph entropies that are based on a novel information functional, which is the number of vertices of different degree together with the number of edges between different degree vertices. In this paper, we study the chemical graph of crystal structure of titanium difluoride TiF 2 and crystallographic structure of cuprite Cu 2 O . Also, we compute entropies of these structures by making a relation of degree based topological indices namely first redefined Zagreb index, second redefined Zagreb index, third redefined Zagreb index, fourth Atom Bond Connectivity index, fifth Geometric Arithmetic index, Sanskruti index with the help of information function.

In this paper, we consider the graph entropy measures based on the number of independent sets and matchings. The reason to study these measures relates to the fact that the independent set and matching problem is computationally demanding. However, these features can be calculated for smaller networks. In case one can establish efficient estimations, those measures may be also used for larger graphs. So, we establish some upper and lower bounds as well as some information inequalities for these information-theoretic quantities. In order to give further evidence, we also generate numerical results to study these measures such as list the extremal graphs for these entropies. Those results reveal the two entropies possess some new features.

Under the fierce competition and budget constraints, most mobile apps are launched without sufficient tests. Thus, there exists a great demand for automated app testing. Recent developments in various machine learning techniques have made automated app testing a promising alternative to manual testing. This work proposes novel approaches for one of the core functionalities of automated app testing: the detection of changes in usage-phases of a mobile app. Because of the flexibility of app development languages and the lack of standards, each mobile app is very different from other apps. Furthermore, the graphical user interfaces for similar functionalities are rarely consistent or similar. Thus, we propose methods detecting usage-phase changes through object recognition and metrics utilizing graphs and generative models. Contrary to the existing change detection methods requiring learning models, the proposed methods eliminate the burden of training models. This elimination of training is suitable for mobile app testing whose typical usage-phase is composed of less than 10 screenshots. Our experimental results on commercial mobile apps show promising improvement over the state-of-the-practice method based on SIFT (scale-invariant feature transform).

A fullerene is a cubic three-connected graph whose faces are entirely composed of pentagons and hexagons. Entropy applied to graphs is one of the significant approaches to measuring the complexity of relational structures. Recently, the research on complex networks has received great attention, because many complex systems can be modelled as networks consisting of components as well as relations among these components. Information—theoretic measures have been used to analyze chemical structures possessing bond types and hetero-atoms. In the present article, we reviewed various entropy-based measures on fullerene graphs. In particular, we surveyed results on the topological information content of a graph, namely the orbit-entropy Ia(G), the symmetry index, a degree-based entropy measure Iλ(G), the eccentric-entropy Ifσ(G) and the Hosoya entropy H(G).

Let G be a connected graph. The eccentricity of vertex v is the maximum distance between v and other vertices of G. In this paper, we study a new version of graph entropy based on eccentricity of vertices of G. In continuing, we study this graph entropy for some classes of graph operations. Finally, we compute the graph entropy of two classes of fullerene graphs.

With the fast development of many event-based social networks (EBSNs), event recommendation, which is to recommend a list of upcoming events to a user according to his preference, has attracted a lot of attentions in both academia and industry. In this paper, we propose a successive event recommendation based on graph entropy (SERGE) to deal with the new event cold start problem by exploiting diverse relations as well as asynchronous feedbacks in EBSNs. The SERGE creates recommendation lists at discrete times during each publication period. At the beginning, it constructs a primary graph (PG) based on the entities and their relations in an EBSN and computes the user-event similarity scores by applying a random walk with restart (RWR) algorithm on PG. At each recommendation time, it then constructs a feedback graph (FG) based on the up-to-date user feedbacks on event reservations and applies the RWR again on FG to compute new user-event similarity scores. We then propose to weight the two sets of similarity scores with the graph entropies of both PG and FG and create the final recommendation lists accordingly. We have crawled two datasets from a real EBSN for two cities, Beijing and Shanghai in China. Experimental results validate the effectiveness and superiority of the proposed SERGE scheme over the peer schemes.

The graph entropy was proposed by Körner in the year 1973 when he was studying the problem of coding in information theory. The foundation of graph entropy is in information theory, but it was demonstrated to be firmly identified with some established and often examined graph-theoretic ideas. For instance, it gives an equal definition to a graph to be flawless, and it can likewise be connected to acquire lower bounds in graph covering problems. The objective of this study is to solve the open problem suggested by Kwun et al. in 2018. In this paper, we study the weighted graph entropy by taking augmented Zagreb edge weight and give bounds of it for regular, connected, bipartite, chemical, unicyclic, etc., graphs. Moreover, we compute the weighted graph entropy of certain nanotubes and plot our results to see dependence of weighted entropy on involved parameters.

[Abstract] In this paper we focus on the issue related to finding the resolving connected dominating sets (RCDSs) of a graph, denoted by G. The connected dominating set (CDS) is a connected subset of vertices of G selected to guarantee that all vertices in the graph are connected to vertices in the CDS. The connected dominating set with minimum cardinality, or minimum CDS (MCDS), is an adequate virtual backbone for information interchange in a network. When distinct vertices of G have also distinct representations with respect to a subset of vertices in the MCDS, it is said that the MCDS includes a resolving set (RS) of G. With this work, we explore different strategies to find the RCDS with minimum cardinality in complex networks where the vertices have different importances. Xunta de Galicia; ED431C 2016-045 Xunta de Galicia; ED341D R2016/012 Xunta de Galicia; ED431G/01 Agencia Estatal de Investigación de España; TEC2013-47141-C4-1-R Agencia Estatal de Investigación de España; TEC2015-69648-REDC Agencia Estatal de Investigación de España; TEC2016-75067-C4-1-R

The performance evaluation of virtual network embedding (VNE) has appeared to be meaningful, with the increase of VNE algorithms. This paper proposes a framework of evaluating VNE algorithms using graph entropy theory. Also, conducts a set of simulation experiments based on Alevin platform to obtain the input data for performance evaluation of algorithms. In the process of computing the weights of evaluational indexes using graph entropy theory, two problems, namely, the different dimension of the index data and the weak relationship between indexes, have been encountered. Therefore, the evaluational indexes are nondimensionalized and the covariance matrix of indexes is employed to express the association between the evaluational indexes of VNE algorithms. Then, the weights of evaluational indexes are obtained through a process of, constructing the adjacency matrix, establishing the information function and calculating the information entropy of network nodes. Consequently, the performance evaluation for VNE algorithms is implemented using the weights of evaluational indexes.

The degree-based entropy of a graph is defined as the Shannon entropy based on the information functional that associates the vertices of the graph with the corresponding degrees. We obtain the maximum value of the degree-based entropy among bipartite graphs with n vertices and and m edges by characterizing corresponding degree sequences. This implies the known result due to Cao et al. (2014) that the path attains the maximum degree-based entropy among trees with n vertices.

OLAP (On-line Analytical Processing) can provide users with aggregate results from different perspectives and granularities. With the advent of heterogeneous information networks that consist of multi-type, interconnected nodes, such as bibliographic networks and knowledge graphs, it is important to study flexible aggregation in such networks. The aggregation results by existing work are limited to one type of node, which cannot be applied to aggregation on multi-type nodes, and relations in large-scale heterogeneous information networks. In this paper, we investigate the flexible aggregation problem on large-scale heterogeneous information networks, which is defined on multi-type nodes and relations. Moreover, by considering both attributes and structures, we propose a novel function based on graph entropy to measure the similarities of nodes. Further, we prove that the aggregation problem based on the function is NP-hard. Therefore, we develop an efficient heuristic algorithm for aggregation in two phases: informational aggregation and structural aggregation. The algorithm has linear time and space complexity. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of the proposed algorithm.

In this paper, we present a detailed framework to analyze the evolution of the random topology of a time-varying wireless network via the information theoretic notion of entropy rate. We consider a propagation channel varying over time with random node positions in a closed space and Rayleigh fading affecting the connections between nodes. The existence of an edge between two nodes at given locations is modeled by a Markov chain, enabling memory effects in network dynamics. We then derive a lower and an upper bound on the entropy rate of the spatiotemporal network. The entropy rate measures the shortest per-step description of the stationary stochastic process defining the state of the wireless system and depends both on the maximum Doppler shift and the path loss exponent. It characterizes the topological uncertainty of the wireless network and quantifies how quickly the underlying topology is varying with time., Comment: 6 pages, 6 figures, IEEE Global Communications Conference (GLOBECOM), in press, 2018

Combinatoric measures of entropy capture the complexity of a graph but rely upon the calculation of its independent sets, or collections of non-adjacent vertices. This decomposition of the vertex set is a known NP-Complete problem and for most real world graphs is an inaccessible calculation. Recent work by Dehmer et al. and Tee et al. identified a number of vertex level measures that do not suffer from this pathological computational complexity, but that can be shown to be effective at quantifying graph complexity. In this paper, we consider whether these local measures are fundamentally equivalent to global entropy measures. Specifically, we investigate the existence of a correlation between vertex level and global measures of entropy for a narrow subset of random graphs. We use the greedy algorithm approximation for calculating the chromatic information and therefore K&ouml, rner entropy. We are able to demonstrate strong correlation for this subset of graphs and outline how this may arise theoretically.

The characterization of topological uncertainty in wireless networks using the formalism of graph entropy has received interest in the spatial networks community. In this paper, we develop lower bounds on the entropy of a wireless network by conditioning on potential network observables. Two approaches are considered: 1) conditioning on subgraphs, and 2) conditioning on node positions. The first approach is shown to yield a relatively tight bound on the network entropy. The second yields a loose bound, in general, but it provides insight into the dependence between node positions (modelled using a homogeneous binomial point process in this work) and the network topology.

For embedding virtual networks into a large scale substrate network, a massive amount of time is needed to search the resource space even if the scale of the virtual network is small. The complexity of searching the candidate resource will be reduced if candidates in substrate network can be located in a group of particularly matched areas, in which the resource distribution and communication structure of the substrate network exhibit a maximal similarity with the objective virtual network. This work proposes to discover the optimally suitable resource in a substrate network corresponding to the objective virtual network through comparison of their graph entropies. Aiming for this, the substrate network is divided into substructures referring to the importance of nodes in it, and the entropies of these substructures are calculated. The virtual network will be embedded preferentially into the substructure with the closest entropy if the substrate resource satisfies the demand of the virtual network. The experimental results validate that the efficiency of virtual network embedding can be improved through our proposal. Simultaneously, the quality of embedding has been guaranteed without significant degradation.

The alcoholism can be detected by analyzing electroencephalogram (EEG) signals. However, analyzing multi-channel EEG signals is a challenging task, which often requires complicated calculations and long execution time. This paper proposes three data selection methods to extract representative data from the EEG signals of alcoholics. The methods are the principal component analysis based on graph entropy (PCA-GE), the channel selection based on graph entropy (GE) difference, and the mathematic combinations channel selection, respectively. For comparison purposes, the selected data from the three methods are then classified by three classifiers: the J48 decision tree, the K-nearest neighbor and the Kstar, separately. The experimental results show that the proposed methods are successful in selecting data without compromising the classification accuracy in discriminating the EEG signals from alcoholics and non-alcoholics. Among them, the proposed PCA-GE method uses only 29.69 % of the whole data and 29.5 % of the computation time but achieves a 94.5 % classification accuracy. The channel selection method based on the GE difference also gains a 91.67 % classification accuracy by using only 29.69 % of the full size of the original data. Using as little data as possible without sacrificing the final classification accuracy is useful for online EEG analysis and classification application design.

[Abstract] The computation of a set constituted by few vertices to define a virtual backbone supporting information interchange is a problem that arises in many areas when analysing networks of different natures, like wireless, brain, or social networks. Recent papers propose obtaining such a set of vertices by computing the connected dominating set (CDS) of a graph. In recent works, the CDS has been obtained by considering that all vertices exhibit similar characteristics. However, that assumption is not valid for complex networks in which their vertices can play different roles. Therefore, we propose finding the CDS by taking into account several metrics which measure the importance of each network vertex e.g., error probability, entropy, or entropy variation (EV). Galicia. Consellería de Cultura, Educación e Ordenación Universitaria; ED431C 2016-045 Galicia. Consellería de Cultura, Educación e Ordenación Universitaria; ED341DR2016/012 Agencia Estatal de Investigación (España); TEC2015-69648-REDC Agencia Estatal de Investigación (España); TEC2016-75067-C4-1-R Agencia Estatal de Investigación (España); TIN2017-85160-C2-1-R

Behavioral economics show us that emotions play an important role in individual behavior and decision-making. Does this also affect collective decision making in a community? Here we investigate whether the community sentiment energy of a topic is related to the spreading popularity of the topic. To compute the community sentiment energy of a topic, we first analyze the sentiment of a user on the key phrases of the topic based on the recent tweets of the user. Then we compute the total sentiment energy of all users in the community on the topic based on the Markov Random Field (MRF) model and graph entropy model. Experiments on two communities find the linear correlation between the community sentiment energy and the real spreading popularity of topics. Based on the finding, we proposed two models to predict the popularity of topics. Experimental results show the effectiveness of the two models and the helpful of sentiment in predicting the popularity of topics. Experiments also show that community sentiment affects collective decision making of spreading a topic or not in the community., Journal of Intelligent Information Systems

Graph entropies have been introduced to quantitatively measure the structural information content of graphs and networks; they have plenty of applications in various fields. Utilizing the number of subgraphs to establish measures for determining the complexity of molecular graphs are also prevalent in the study of mathematical chemistry. In this paper, we develop a new graph entropy measure that is based on the number of spanning forests. We prove explicit expressions for the entropy for trees, unicyclic and bicyclic graphs, and show that the cycle graph Cn attains the maximal value of the entropy for unicyclic graphs with order n and large cycle lengths. Based on generating numerical results, we conjecture extremal unicyclic graphs with respect to the entropy as well as we compare the values of our entropy for c-cyclic graphs, and generate graphs of bicyclic graphs and tricyclic graphs with 6 vertices for performing further research.

We propose an entropy function for simplicial complices. Its value gives the expected cost of the optimal encoding of sequences of vertices of the complex, when any two vertices belonging to the same simplex are indistinguishable. We focus on the computational properties of the entropy function, showing that it can be computed efficiently. Several examples over complices consisting of hundreds of simplices show that the proposed entropy function can be used in the analysis of large sequences of simplicial complices that often appear in computational topology applications.

Inspired by the generalized entropies for graphs, a class of generalized degree-based graph entropies is proposed using the known information-theoretic measures to characterize the structure of complex networks. The new entropies depend on assigning a probability distribution about the degrees to a network. In this paper, some extremal properties of the generalized degree-based graph entropies by using the degree powers are proved. Moreover, the relationships among the entropies are studied. Finally, numerical results are presented to illustrate the features of the new entropies.

Many graph invariants have been used for the construction of entropy-based measures to characterize the structure of complex networks. The starting point has been always based on assigning a probability distribution to a network when using Shannon’s entropy. In particular, Cao et al. (2014 and 2015) defined special graph entropy measures which are based on degrees powers. In this paper, we obtain some lower and upper bounds for these measures and characterize extremal graphs. Moreover we resolve one part of a conjecture stated by Cao et al.

We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing ITLB + o(ITLB) + O(n) comparisons in the worst case. Here, n denotes the size of the ground sets, and ITLB denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target partial order. Our approach is to replace the target partial order by a weak order (that is, a partial order with a layered structure) extending it, without increasing the information theoretic lower bound too much. We then solve the problem by applying an efficient multiple selection algorithm. The overall complexity of our algorithm is polynomial. This answers a question of Yao (SIAM J. Comput. 18, 1989). We base our analysis on the entropy of the target partial order, a quantity that can be efficiently computed and provides a good estimate of the information-theoretic lower bound., Referees' comments incorporated

In this paper, we study several distance-based entropy measures on fullerene graphs. These include the topological information content of a graph I a ( G ) , a degree-based entropy measure, the eccentric-entropy I f σ ( G ) , the Hosoya entropy H ( G ) and, finally, the radial centric information entropy H e c c . We compare these measures on two infinite classes of fullerene graphs denoted by A 12 n + 4 and B 12 n + 6 . We have chosen these measures as they are easily computable and capture meaningful graph properties. To demonstrate the utility of these measures, we investigate the Pearson correlation between them on the fullerene graphs.

In this paper we extend earlier results on Hosoya entropy (H-entropy) of graphs, and establish connections between H-entropy and automorphisms of graphs. In particular, we determine the H-entropy of graphs whose automorphism group has exactly two orbits, and characterize some classes of graphs with zero H-entropy.

This paper introduces a variant of entropy measures based on vertex eccentricity and applies it to all graphs representing the isomers of octane. Taking into account the vertex degree as well (degree-ecc-entropy), we find a good correlation with the acentric factor of octane isomers. In particular, we compute the degree-ecc-entropy for three classes of dendrimer graphs.