Identifying influential nodes in complex networks is of both theoretical and practical importance. Existing methods identify influential nodes based on their positions in the network and assume that the nodes are homo...Identifying influential nodes in complex networks is of both theoretical and practical importance. Existing methods identify influential nodes based on their positions in the network and assume that the nodes are homogeneous. However, node heterogeneity （i.e., different attributes such as interest, energy, age, and so on ） ubiquitously exists and needs to be taken into consideration. In this paper, we conduct an investigation into node attributes and propose a graph signal pro- cessing based centrality （GSPC） method to identify influential nodes considering both the node attributes and the network topology. We first evaluate our GSPC method using two real-world datasets. The results show that our GSPC method effectively identifies influential nodes, which correspond well with the underlying ground truth. This is compatible to the previous eigenvector centrality and principal component centrality methods under circumstances where the nodes are homogeneous. In addition, spreading analysis shows that the GSPC method has a positive effect on the spreading dynamics.展开更多
In this paper the structure of neighborhood complex of a bipartite graph is discussed, the concept of dusl complex is introduced, the main result that a pair of dual complexes is exactly the neighborhood complex or a ...In this paper the structure of neighborhood complex of a bipartite graph is discussed, the concept of dusl complex is introduced, the main result that a pair of dual complexes is exactly the neighborhood complex or a connected bipartite graph is proved.展开更多
We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By c...We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp #P hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as graph embeddings, discrete Morse theory and graph clustering.展开更多
Let T be the subgroup of the multiplicative group C^(×)consisting of all complex numbers z with|z|=1.A T-gain graph is a tripleΦ=(G,T,φ)(or short for(G,φ))consisting of a simple graph G=(V,E),as the underlying...Let T be the subgroup of the multiplicative group C^(×)consisting of all complex numbers z with|z|=1.A T-gain graph is a tripleΦ=(G,T,φ)(or short for(G,φ))consisting of a simple graph G=(V,E),as the underlying graph of(G,Φ),the circle group T and a gain functionΦ:→E→T such that φ(vivj)=φ(vjvi) for any adjacent vertices vi and vj.Let i+(G,φ)(resp.,i+(G))be the positive inertia index of(G,φ)(resp.,G).In this paper,we prove that-c(G)≤i+(G,φ)-i+(G)≤c(G),where c(G)is the cyclomatic number of G,and characterize all the corresponding extremal graphs.展开更多
The precise and effective measure results of Web applications not only facilitate good comprehension of them, but also benefit to the macro-management of software activities, such as testing, reverse engineering, reus...The precise and effective measure results of Web applications not only facilitate good comprehension of them, but also benefit to the macro-management of software activities, such as testing, reverse engineering, reuse, etc. The paper exploits some researches on measuring the structure complexity of Web application. Through a deep analysis of the configuration and objects＇ interactions of Web system, two conclusions have been drawn：① A generic Web application consists of static web page, dynamic page, component and database object; ② The main interactions have only three styles, that is static link, dynamic link and call/return relation. Based on analysis and modeling of the content of a Web page （static or dynamic）, complexity measure methods of both control logic of script and nesting of HTML code are further discussed. In addition, two methods for measuring the complexity of inte〉page navigation are also addressed by modeling the inte〉page navigation behaviors of Web application via WNG graph.展开更多
Following the growing research interests in complex networks, in recent years many researchers treated static structures of software as complex networks and revealed that most of these networks demonstrate small-world...Following the growing research interests in complex networks, in recent years many researchers treated static structures of software as complex networks and revealed that most of these networks demonstrate small-world effect and follow scale-free degree distribution. Different from the perspectives adopted in these works, our previous work proposed software mirror graph to model the dynamic execution processes of software and revealed software mirror graph may also be small world and scale-free. To explain how the software mirror graph evolves into a small world and scale free structure, in this paper we further proposed a mathematical model based on the mechanisms of growth, preferential attachment, and walking. This model captures some of the features of the software mirror graph, and the simulation results show that it can generate a network having similar properties to the software mirror graph. The implications are also discussed in this paper.展开更多
Several possible definitions of local injectivity for a homomorphism of an oriented graph G to an oriented graph H are considered. In each case, we determine the complexity of deciding whether there exists such a homo...Several possible definitions of local injectivity for a homomorphism of an oriented graph G to an oriented graph H are considered. In each case, we determine the complexity of deciding whether there exists such a homomorphism when G is given and H is a fixed tournament on three or fewer vertices. Each possible definition leads to a locally-injective oriented colouring problem. A dichotomy theorem is proved in each case.展开更多
The study investigated user experience, display complexity, display type (tables versus graphs), and task difficulty as variables affecting the user’s ability to navigate through complex visual data. A total of 64 pa...The study investigated user experience, display complexity, display type (tables versus graphs), and task difficulty as variables affecting the user’s ability to navigate through complex visual data. A total of 64 participants, 39 undergraduate students (novice users) and 25 graduate students (intermediate-level users) participated in the study. The experimental design was 2 × 2 × 2 × 3 mixed design using two between-subject variables (display complexity, user experience) and two within-subject variables (display format, question difficulty). The results indicated that response time was superior for graphs (relative to tables), especially when the questions were difficult. The intermediate users seemed to adopt more extensive search strategies than novices, as revealed by an analysis of the number of changes they made to the display prior to answering questions. It was concluded that designers of data displays should consider the (a) type of display, (b) difficulty of the task, and (c) expertise level of the user to obtain optimal levels of performance.展开更多
基金supported by the National Natural Science Foundation of China(Grant No.61231010)the Fundamental Research Funds for the Central Universities,China(Grant No.HUST No.2012QN076)
文摘Identifying influential nodes in complex networks is of both theoretical and practical importance. Existing methods identify influential nodes based on their positions in the network and assume that the nodes are homogeneous. However, node heterogeneity （i.e., different attributes such as interest, energy, age, and so on ） ubiquitously exists and needs to be taken into consideration. In this paper, we conduct an investigation into node attributes and propose a graph signal pro- cessing based centrality （GSPC） method to identify influential nodes considering both the node attributes and the network topology. We first evaluate our GSPC method using two real-world datasets. The results show that our GSPC method effectively identifies influential nodes, which correspond well with the underlying ground truth. This is compatible to the previous eigenvector centrality and principal component centrality methods under circumstances where the nodes are homogeneous. In addition, spreading analysis shows that the GSPC method has a positive effect on the spreading dynamics.
文摘In this paper the structure of neighborhood complex of a bipartite graph is discussed, the concept of dusl complex is introduced, the main result that a pair of dual complexes is exactly the neighborhood complex or a connected bipartite graph is proved.
文摘We generalize Biggs Theorem to the case of directed cycles of multi-digraphs allowing to compute the dimension of the directed cycle space independently of the graph representation with linear runtime complexity. By considering two-dimensional CW complex of elementary cycles and deriving formulas for the Betti numbers of the associated cellular homology groups, we extend the list of representation independent topological inavariants measuring the graph structure. We prove the computation of the 2nd Betti number to be sharp #P hard in general and present specific representation invariant sub-fillings yielding efficiently computable homology groups. Finally, we suggest how to use the provided structural measures to shed new light on graph theoretical problems as graph embeddings, discrete Morse theory and graph clustering.
基金Supported by the National Natural Science Foundation of China(Grant No.11971474)the Natural Science Foundation of Shandong Province(Grant No.ZR2019BA016)。
文摘Let T be the subgroup of the multiplicative group C^(×)consisting of all complex numbers z with|z|=1.A T-gain graph is a tripleΦ=(G,T,φ)(or short for(G,φ))consisting of a simple graph G=(V,E),as the underlying graph of(G,Φ),the circle group T and a gain functionΦ:→E→T such that φ(vivj)=φ(vjvi) for any adjacent vertices vi and vj.Let i+(G,φ)(resp.,i+(G))be the positive inertia index of(G,φ)(resp.,G).In this paper,we prove that-c(G)≤i+(G,φ)-i+(G)≤c(G),where c(G)is the cyclomatic number of G,and characterize all the corresponding extremal graphs.
基金Supported by the Defense Pre-Research Project ofthe 10th Five-Year Plan of China (413150902) ,andthe Defense Pre-Research Project of the Navy Equipment Ministry (10104010201)
文摘The precise and effective measure results of Web applications not only facilitate good comprehension of them, but also benefit to the macro-management of software activities, such as testing, reverse engineering, reuse, etc. The paper exploits some researches on measuring the structure complexity of Web application. Through a deep analysis of the configuration and objects＇ interactions of Web system, two conclusions have been drawn：① A generic Web application consists of static web page, dynamic page, component and database object; ② The main interactions have only three styles, that is static link, dynamic link and call/return relation. Based on analysis and modeling of the content of a Web page （static or dynamic）, complexity measure methods of both control logic of script and nesting of HTML code are further discussed. In addition, two methods for measuring the complexity of inte〉page navigation are also addressed by modeling the inte〉page navigation behaviors of Web application via WNG graph.
文摘Following the growing research interests in complex networks, in recent years many researchers treated static structures of software as complex networks and revealed that most of these networks demonstrate small-world effect and follow scale-free degree distribution. Different from the perspectives adopted in these works, our previous work proposed software mirror graph to model the dynamic execution processes of software and revealed software mirror graph may also be small world and scale-free. To explain how the software mirror graph evolves into a small world and scale free structure, in this paper we further proposed a mathematical model based on the mechanisms of growth, preferential attachment, and walking. This model captures some of the features of the software mirror graph, and the simulation results show that it can generate a network having similar properties to the software mirror graph. The implications are also discussed in this paper.
文摘Several possible definitions of local injectivity for a homomorphism of an oriented graph G to an oriented graph H are considered. In each case, we determine the complexity of deciding whether there exists such a homomorphism when G is given and H is a fixed tournament on three or fewer vertices. Each possible definition leads to a locally-injective oriented colouring problem. A dichotomy theorem is proved in each case.
文摘The study investigated user experience, display complexity, display type (tables versus graphs), and task difficulty as variables affecting the user’s ability to navigate through complex visual data. A total of 64 participants, 39 undergraduate students (novice users) and 25 graduate students (intermediate-level users) participated in the study. The experimental design was 2 × 2 × 2 × 3 mixed design using two between-subject variables (display complexity, user experience) and two within-subject variables (display format, question difficulty). The results indicated that response time was superior for graphs (relative to tables), especially when the questions were difficult. The intermediate users seemed to adopt more extensive search strategies than novices, as revealed by an analysis of the number of changes they made to the display prior to answering questions. It was concluded that designers of data displays should consider the (a) type of display, (b) difficulty of the task, and (c) expertise level of the user to obtain optimal levels of performance.
