Vertex Clustering of Augmented Graph Streams

In this paper we propose a graph stream clustering algorithm with a unied similarity measure on both structural and attribute properties of vertices, with each attribute being treated as a vertex. Unlike others, our approach does not require an input parameter for the number of clusters, instead, it dynamically creates new sketch-based clusters and periodically merges existing similar clusters. Experiments on two publicly available datasets reveal the advantages of our approach in detecting vertex clusters in the graph stream. We provide a detailed investigation into how parameters affect the algorithm performance. We also provide a quantitative evaluation and comparison with a well-known offline community detection algorithm which shows that our streaming algorithm can achieve comparable or better average cluster purity.

Using Graph Components Derived from an Associative Concept Dictionary to Predict fMRI Neural Activation Patterns that Represent the Meaning of Nouns

In this study, we introduce an original distance definition for graphs, called the Markov-inverse-F measure (MiF). This measure enables the integration of classical graph theory indices with new knowledge pertaining to structural feature extraction from semantic networks. MiF improves the conventional Jaccard and/or Simpson indices, and reconciles both the geodesic information (random walk) and co-occurrence adjustment (degree balance and distribution). We measure the effectiveness of graph-based coefficients through the application of linguistic graph information for a neural activity recorded during conceptual processing in the human brain. Specifically, the MiF distance is computed between each of the nouns used in a previous neural experiment and each of the in-between words in a subgraph derived from the Edinburgh Word Association Thesaurus of English. From the MiF-based information matrix, a machine learning model can accurately obtain a scalar parameter that specifies the degree to which each voxel in (the MRI image of) the brain is activated by each word or each principal component of the intermediate semantic features. Furthermore, correlating the voxel information with the MiF-based principal components, a new computational neurolinguistics model with a network connectivity paradigm is created. This allows two dimensions of context space to be incorporated with both semantic and neural distributional representations.

Memory-centric VDF Graph Transformations for Practical FPGA Implementation

Realising memory intensive applications such as image and video processing on FPGA requires creation of complex, multi-level memory hierarchies to achieve real-time performance; however commerical High Level Synthesis tools are unable to automatically derive such structures and hence are unable to meet the demanding bandwidth and capacity constraints of these applications. Current approaches to solving this problem can only derive either single-level memory structures or very deep, highly inefficient hierarchies, leading in either case to one or more of high implementation cost and low performance. This paper presents an enhancement to an existing MC-HLS synthesis approach which solves this problem; it exploits and eliminates data duplication at multiple levels levels of the generated hierarchy, leading to a reduction in the number of levels and ultimately higher performance, lower cost implementations. When applied to synthesis of C-based Motion Estimation, Matrix Multiplication and Sobel Edge Detection applications, this enables reductions in Block RAM and Look Up Table (LUT) cost of up to 25%, whilst simultaneously increasing throughput.

Parkinson’s Is Time on Your Side? Evidence for Difficulties with Sensorimotor Synchronization

There is lack of consistent evidence as to how well PD patients are able to accurately time their movements across space with an external acoustic signal. For years, research based on the finger-tapping paradigm, the most popular paradigm for exploring the brain's ability to time movement, has provided strong evidence that patients are not able to accurately reproduce an isochronous interval [i.e., Ref. (1)]. This was undermined by Spencer and Ivry (2) who suggested a specific deficit in temporal control linked to emergent, rhythmical movement not event-based actions, which primarily involve the cerebellum. In this study, we investigated motor timing of seven idiopathic PD participants in event-based sensorimotor synchronization task. Participants were asked to move their finger horizontally between two predefined target zones to synchronize with the occurrence of two sound events at two time intervals (1.5 and 2.5 s). The width of the targets and the distance between them were manipulated to investigate impact of accuracy demands and movement amplitude on timing performance. The results showed that participants with PD demonstrated specific difficulties when trying to accurately synchronize their movements to a beat. The extent to which their ability to synchronize movement was compromised was found to be related to the severity of PD, but independent of the spatial constraints of the task.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

Necessary and sufficient conditions for a Hamiltonian graph

A graph is singular if the zero eigenvalue is in the spectrum of its 0-1 adjacency matrix A. If an eigenvector belonging to the zero eigenspace of A has no zero entries, then the singular graph is said to be a core graph. A ( k,t)-regular set is a subset of the vertices inducing a k -regular subgraph such that every vertex not in the subset has t neighbours in it. We consider the case when k=t which relates to the eigenvalue zero under certain conditions. We show that if a regular graph has a ( k,k )-regular set, then it is a core graph. By considering the walk matrix we develop an algorithm to extract ( k,k )-regular sets and formulate a necessary and sufficient condition for a graph to be Hamiltonian.

Spectra of graphs obtained by a generalization of the join graph operation

Taking a Fiedler’s result on the spectrum of a matrix formed from two symmetric matrices as a motivation, a more general result is deduced and applied to the determination of adjacency and Laplacian spectra of graphs obtained by a generalized join graph operation on families of graphs (regular in the case of adjacency spectra and arbitrary in the case of Laplacian spectra). Some additional consequences are explored, namely regarding the largest eigenvalue and algebraic connectivity.

Gene Network Inference using Machine Learning and Graph Algorithms on Big Biomedical Data

Thesis (Master's)--University of Washington, 2016-03

A Fractional Perspective to the Bond Graph Modelling of World Economies

Inspired in dynamic systems theory and Brewer’s contributions to apply it to economics, this paper establishes a bond graph model. Two main variables, a set of inter-connectivities based on nodes and links (bonds) and a fractional order dynamical perspective, prove to be a good macro-economic representation of countries’ potential performance in nowadays globalization. The estimations based on time series for 50 countries throughout the last 50 decades confirm the accuracy of the model and the importance of scale for economic performance.

Graph usage in financial reports: Evidence from Portuguese listed companies

When assessing investment options, investors focus on the graphs of annual reports, despite lack of auditing. If poorly constructed, graphs distort perceptions and lead to inaccurate decisions. This study examines graph usage in all the companies listed on Euronext Lisbon in 2013. The findings suggest that graphs are common in the annual reports of Portuguese companies and that, while there is no evidence of Selectivity Distortion, both Measurement and Orientation Distortions are pervasive. The study recommends the auditing of financial graphs, and urges preparers and users of annual reports to be wary of the possibility of graph distortion.

Graph usage in annual reports, evidence from Norwegian listed companies

As investors and other users of annual reports often focus their attention on graphs, it is important that they portray accurate and reliable information. However, previous studies show that graphs often distort information and mislead users. This study analyses graph usage in annual reports from the 52 most traded Norwegian companies. The findings suggest that Norwegian companies commonly use graphs, and that the graph distortions, presentational enhancement and measurement distortion, are present. No evidence of selectivity was found. This study recommends development of guidelines for graphical disclosure, and advises preparers and users of annual reports to be aware of misleading graphs.

The effectiveness of a multisensory writing program in improving cursive writing ability in children with sensorimotor difficulties

It is estimated that five to ten percent of children experience sensory motor difficulties that result in various learnlng disabilitiies , among them. inabllity to output Information on paper in the appropriate manner (Ayres ,1985). The relationship between sensorimotorabillty and handwriting is well documented in the literature (Freeman,1917; Townsend , 1951; Nlkola-Ll sa, 1987). While much of the literature is inconclusive, there are findings to suggest that muitisensory handwriting programmes are an effective approach to improvlng writing abIlity in these chlldren. For a number of years, Occupational Therapists have been involved in the remediation of handwriting utllizing , amongst other approaches . multisensory programmes. While subjective assessments of effectiveness have been extremerly positive. scientIfic evaluation has been minimal . If further intervention in this area is to occur, it Is essential that the profession be able to justify the existence of such programmes . The purpose of this study was to examine what effects a multlsensory writing prog~am would have on the curslve writing ability of chlldren with sensorimotor dlfficulties. A single case with multiple baselines across be havlours design was used , with the behavlours being cursive writing abilIty of fIve distInct letter groups. The fIve groups were taught in random order, one group every two weeks , In a one-hour session. Repeated measurements of writing speed and qualIty for each letter group were made. This design was repeated over three other cases . Results of the study yielded statistical signifi cance in trend changes In specIfic letter groups for all of the chlldren following interventlon. One child achieved statistical significance In the overall change In quality , while none of the children achieved overall statistical significance In speed score changes . Teacher reports and an assessment of written language prior to and following the program suggest that Intervention may have had a positive effect on self-confidence in written output, and on the maturlty of written expression in some of the cases . Further research in this field is needed to validate the continual use of multisensory writing programmes by Occupational Theraplsts worklng with this specific population and to provide some directlon with regards to the Integration of multlsensory writing programmes within the regular academic remedial programme .

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.