A lower bound for the energy of symmetric matrices and graphs

The energy of a symmetric matrix is the sum of the absolute values of its eigenvalues. We introduce a lower bound for the energy of a symmetric partitioned matrix into blocks. This bound is related to the spectrum of its quotient matrix. Furthermore, we study necessary conditions for the equality. Applications to the energy of the generalized composition of a family of arbitrary graphs are obtained. A lower bound for the energy of a graph with a bridge is given. Some computational experiments are presented in order to show that, in some cases, the obtained lower bound is incomparable with the well known lower bound $2\sqrt{m}$, where $m$ is the number of edges of the graph.

Real-time alert correlation with type graphs

The premise of automated alert correlation is to accept that false alerts from a low level intrusion detection system are inevitable and use attack models to explain the output in an understandable way. Several algorithms exist for this purpose which use attack graphs to model the ways in which attacks can be combined. These algorithms can be classified in to two broad categories namely scenario-graph approaches, which create an attack model starting from a vulnerability assessment and type-graph approaches which rely on an abstract model of the relations between attack types. Some research in to improving the efficiency of type-graph correlation has been carried out but this research has ignored the hypothesizing of missing alerts. Our work is to present a novel type-graph algorithm which unifies correlation and hypothesizing in to a single operation. Our experimental results indicate that the approach is extremely efficient in the face of intensive alerts and produces compact output graphs comparable to other techniques.

Direct experimental evidence for a multiparticle-hole ground state configuration of deformed Mg-33

The first direct experimental evidence of a multiparticle-hole ground state configuration of the neutron-rich Mg-33 isotope has been obtained via intermediate energy (400 A MeV) Coulomb dissociation measurement. The major part similar to(70 +/- 13)% of the cross section is observed to populate the excited states of Mg-32 after the Coulomb breakup of Mg-33. The shapes of the differential Coulomb dissociation cross sections in coincidence with different core excited states favor that the valence neutron occupies both the s(1/2) and p(3/2) orbitals. These experimental findings suggest a significant reduction and merging of sd-pf shell gaps at N similar to 20 and 28. The ground state configuration of Mg-33 is predominantly a combination of Mg-32(3.0,3.5MeV; 2(-), 1(-)) circle times nu(s1/2), Mg-32(2.5MeV; 2(+)) circle times nu(p3/2), and Mg-32(0; 0(+)) circle times nu(p3/2). The experimentally obtained quantitative spectroscopic information for the valence neutron occupation of the s and p orbitals, coupled with different core states, is in agreement with Monte Carlo shell model (MCSM) calculation using 3 MeV as the shell gap at N = 20.

A SURVEY OF DISTANCE MAGIC GRAPHS

In this report, we survey results on distance magic graphs and some closely related graphs. A distance magic labeling of a graph G with magic constant k is a bijection l from the vertex set to {1, 2, . . . , n}, such that for every vertex x Σ l(y) = k,y∈NG(x) where NG(x) is the set of vertices of G adjacent to x. If the graph G has a distance magic labeling we say that G is a distance magic graph. In Chapter 1, we explore the background of distance magic graphs by introducing examples of magic squares, magic graphs, and distance magic graphs. In Chapter 2, we begin by examining some basic results on distance magic graphs. We next look at results on different graph structures including regular graphs, multipartite graphs, graph products, join graphs, and splitting graphs. We conclude with other perspectives on distance magic graphs including embedding theorems, the matrix representation of distance magic graphs, lifted magic rectangles, and distance magic constants. In Chapter 3, we study graph labelings that retain the same labels as distance magic labelings, but alter the definition in some other way. These labelings include balanced distance magic labelings, closed distance magic labelings, D-distance magic labelings, and distance antimagic labelings. In Chapter 4, we examine results on neighborhood magic labelings, group distance magic labelings, and group distance antimagic labelings. These graph labelings change the label set, but are otherwise similar to distance magic graphs. In Chapter 5, we examine some applications of distance magic and distance antimagic labeling to the fair scheduling of tournaments. In Chapter 6, we conclude with some open problems.

Quantum kernels for unattributed graphs using discrete-time quantum walks

In this paper, we develop a new family of graph kernels where the graph structure is probed by means of a discrete-time quantum walk. Given a pair of graphs, we let a quantum walk evolve on each graph and compute a density matrix with each walk. With the density matrices for the pair of graphs to hand, the kernel between the graphs is defined as the negative exponential of the quantum Jensen–Shannon divergence between their density matrices. In order to cope with large graph structures, we propose to construct a sparser version of the original graphs using the simplification method introduced in Qiu and Hancock (2007). To this end, we compute the minimum spanning tree over the commute time matrix of a graph. This spanning tree representation minimizes the number of edges of the original graph while preserving most of its structural information. The kernel between two graphs is then computed on their respective minimum spanning trees. We evaluate the performance of the proposed kernels on several standard graph datasets and we demonstrate their effectiveness and efficiency.

Random walk with restart over dynamic graphs

Random Walk with Restart (RWR) is an appealing measure of proximity between nodes based on graph structures. Since real graphs are often large and subject to minor changes, it is prohibitively expensive to recompute proximities from scratch. Previous methods use LU decomposition and degree reordering heuristics, entailing O(|V|^3) time and O(|V|^2) memory to compute all (|V|^2) pairs of node proximities in a static graph. In this paper, a dynamic scheme to assess RWR proximities is proposed: (1) For unit update, we characterize the changes to all-pairs proximities as the outer product of two vectors. We notice that the multiplication of an RWR matrix and its transition matrix, unlike traditional matrix multiplications, is commutative. This can greatly reduce the computation of all-pairs proximities from O(|V|^3) to O(|delta|) time for each update without loss of accuracy, where |delta| (<<|V|^2) is the number of affected proximities. (2) To avoid O(|V|^2) memory for all pairs of outputs, we also devise efficient partitioning techniques for our dynamic model, which can compute all pairs of proximities segment-wisely within O(l|V|) memory and O(|V|/l) I/O costs, where 1<=l<=|V| is a user-controlled trade-off between memory and I/O costs. (3) For bulk updates, we also devise aggregation and hashing methods, which can discard many unnecessary updates further and handle chunks of unit updates simultaneously. Our experimental results on various datasets demonstrate that our methods can be 1–2 orders of magnitude faster than other competitors while securing scalability and exactness.

Convergence time to equilibrium distributions of autonomous and periodic non-autonomous graphs

We present some estimates of the time of convergence to the equilibrium distribution in autonomous and periodic non-autonomous graphs, with ergodic stochastic adjacency matrices, using the eigenvalues of these matrices. On this way we generalize previous results from several authors, that only considered reversible matrices.

Representing image captions as concept graphs using semantic information

Conceptual interpretation of languages has gathered peak interest in the world of artificial intelligence. The challenge in modeling various complications involved in a language is the main motivation behind our work. Our main focus in this work is to develop conceptual graphical representation for image captions. We have used discourse representation structure to gain semantic information which is further modeled into a graphical structure. The effectiveness of the model is evaluated by a caption based image retrieval system. The image retrieval is performed by computing subgraph based similarity measures. Best retrievals were given an average rating of . ± . out of 4 by a group of 25 human judges. The experiments were performed on a subset of the SBU Captioned Photo Dataset. This purpose of this work is to establish the cognitive sensibility of the approach to caption representations

Representing image captions as concept graphs using semantic information

Conceptual interpretation of languages has gathered peak interest in the world of artificial intelligence. The challenge in modeling various complications involved in a language is the main motivation behind our work. Our main focus in this work is to develop conceptual graphical representation for image captions. We have used discourse representation structure to gain semantic information which is further modeled into a graphical structure. The effectiveness of the model is evaluated by a caption based image retrieval system. The image retrieval is performed by computing subgraph based similarity measures. Best retrievals were given an average rating of . ± . out of 4 by a group of 25 human judges. The experiments were performed on a subset of the SBU Captioned Photo Dataset. This purpose of this work is to establish the cognitive sensibility of the approach to caption representations.

The role of microcomputer-based laboratory display in supporting the construction of new understanding in kinematics

Teachers' failure to utilise MBL activities more widely may be due to not recognising their capacity to transform the nature of laboratory activities to be more consistent with contemporary constructivist theories of learning. This research aimed to increase understanding of how MBL activities specifically designed to be consistent with a constructivist theory of learning support or constrain student construction of understanding. The first author conducted the research with his Year 11 physics class of 29 students. Dyads completed nine tasks relating to kinematics using a Predict-Observe-Explain format. Data sources included video and audio recordings of students and teacher during four 70-minute sessions, students' display graphs and written notes, semi-structured student interviews, and the teacher's journal. The study identifies the actors and describes the patterns of interactions in the MBL. Analysis of students' discourse and actions identified many instances where students' initial understanding of kinematics were mediated in multiple ways. Students invented numerous techniques for manipulating data in the service of their emerging understanding. The findings are presented as eight assertions. Recommendations are made for developing pedagogical strategies incorporating MBL activities which will likely catalyse student construction of understanding.

An instrument for assessing primary students’ knowledge of information graphics in mathematics

Information graphics have become increasingly important in representing, organising and analysing information in a technological age. In classroom contexts, information graphics are typically associated with graphs, maps and number lines. However, all students need to become competent with the broad range of graphics that they will encounter in mathematical situations. This paper provides a rationale for creating a test to measure students’ knowledge of graphics. This instrument can be used in mass testing and individual (in-depth) situations. Our analysis of the utility of this instrument informs policy and practice. The results provide an appreciation of the relative difficulty of different information graphics; and provide the capacity to benchmark information about students’ knowledge of graphics. The implications for practice include the need to support the development of students’ knowledge of graphics, the existence of gender differences, the role of cross-curriculum applications in learning about graphics, and the need to explicate the links among graphics.

National numeracy tests : a graphic tells a thousand words

Mandatory numeracy tests have become commonplace in many countries, heralding a new era in school assessment. New forms of accountability and an increased emphasis on national and international standards (and benchmarks) have the potential to reshape mathematics curricula. It is noteworthy that the mathematics items used in these tests are rich in graphics. Many of the items, for example, require students to have an understanding of information graphics (e.g., maps, charts and graphs) in order to solve the tasks. This investigation classifies mathematics items in Australia’s inaugural national numeracy tests and considers the effect such standardised testing will have on practice. It is argued that the design of mathematics items are more likely to be a reliable indication of student performance if graphical, linguistic and contextual components are considered both in isolation and in integrated ways as essential elements of task design.

Gender effects in orientation on primary students’ performance on items rich in graphics

This study investigated the longitudinal performance of 378 students who completed mathematics items rich in graphics. Specifically, this study explored student performance across axis (e.g., numbers lines), opposed-position (e.g., line and column graphs) and circular (e.g., pie charts) items over a three-year period (ages 9-11 years). The results of the study revealed significant performance differences in the favour of boys on graphics items that were represented in horizontal and vertical displays. There were no gender differences on items that were represented in a circular manner.