A Scalable General Purpose System for Large-Scale Graph Processing

Graph analytics is an important and computationally demanding class of data analytics. It is essential to balance scalability, ease-of-use and high performance in large scale graph analytics. As such, it is necessary to hide the complexity of parallelism, data distribution and memory locality behind an abstract interface. The aim of this work is to build a scalable graph analytics framework that does not demand significant parallel programming experience based on NUMA-awareness.
The realization of such a system faces two key problems:
(i)~how to develop a scale-free parallel programming framework that scales efficiently across NUMA domains; (ii)~how to efficiently apply graph partitioning in order to create separate and largely independent work items that can be distributed among threads.

A Study of Some Centrality Measures in Graphs

Centrality is in fact one of the fundamental notions in graph theory which has established its close connection with various other areas like Social networks, Flow networks, Facility location problems etc. Even though a plethora of centrality measures have been introduced from time to time, according to the changing demands, the term is not well defined and we can only give some common qualities that a centrality measure is expected to have. Nodes with high centrality scores are often more likely to be very powerful, indispensable, influential, easy propagators of information, significant in maintaining the cohesion of the group and are easily susceptible to anything that disseminate in the network.

Graph analysis of verbal fluency test discriminate between patients with Alzheimer’s disease, Mild Cognitive Impairment and normal elderly controls

Verbal fluency is the ability to produce a satisfying sequence of spoken words during a given time interval. The core of verbal fluency lies in the capacity to manage the executive aspects of language. The standard scores of the semantic verbal fluency test are broadly used in the neuropsychological assessment of the elderly, and different analytical methods are likely to extract even more information from the data generated in this test. Graph theory, a mathematical approach to analyze relations between items, represents a promising tool to understand a variety of neuropsychological states. This study reports a graph analysis of data generated by the semantic verbal fluency test by cognitively healthy elderly (NC), patients with Mild Cognitive Impairment – subtypes amnestic(aMCI) and amnestic multiple domain (a+mdMCI) - and patients with Alzheimer’s disease (AD). Sequences of words were represented as a speech graph in which every word corresponded to a node and temporal links between words were represented by directed edges. To characterize the structure of the data we calculated 13 speech graph attributes (SGAs). The individuals were compared when divided in three (NC – MCI – AD) and four (NC – aMCI – a+mdMCI – AD) groups. When the three groups were compared, significant differences were found in the standard measure of correct words produced, and three SGA: diameter, average shortest path, and network density. SGA sorted the elderly groups with good specificity and sensitivity. When the four groups were compared, the groups differed significantly in network density, except between the two MCI subtypes and NC and aMCI. The diameter of the network and the average shortest path were significantly different between the NC and AD, and between aMCI and AD. SGA sorted the elderly in their groups with good specificity and sensitivity, performing better than the standard score of the task. These findings provide support for a new methodological frame to assess the strength of semantic memory through the verbal fluency task, with potential to amplify the predictive power of this test. Graph analysis is likely to become clinically relevant in neurology and psychiatry, and may be particularly useful for the differential diagnosis of the elderly.

Sosiaalisen median yksilöbrändin merkitys työnhaussa ja yritysten näkökanta työntekijän sosiaalisen median käyttäytymiselle

Työn tavoitteena oli tutkia, kuinka yksilön brändi muodostuu sosiaalisessa mediassa ja mitä sosiaalisen median kanavia suositaan työnhakijoiden ja yritysten keskuudessa. Haettiin myös alueellisilta yrityksiltä vastausta siihen, perehdyttävätkö he uusia työntekijöitä sosiaalisen median käyttäytymisessä. Tietolähteinä käytettiin brändin luomiseen ja sosiaalisen median strategiaan keskittyvää kirjallisuutta sekä yrityksien ja opiskelijoiden haastatteluja. Työn tuloksina todettiin suosituimmiksi kanaviksi itsensä markkinointiin verkostoitumispalvelu LinkedIn. Yritykset korostivat omien projektien merkitystä osaamisen näyttämisessä työnhaussa ja hyvin viestittyä persoonallisuutta hakemuksissa arvostettiin.

Least Median Of Squares Estimation In Power Systems

Static state estimators currently in use in power systems are prone to masking by multiple bad data. This is mainly because the power system regression model contains many leverage points; typically they have a cluster pattern. As reported recently in the statistical literature, only high breakdown point estimators are robust enough to cope with gross errors corrupting such a model. This paper deals with one such estimator, the least median of squares estimator, developed by Rousseeuw in 1984. The robustness of this method is assessed while applying it to power systems. Resampling methods are developed, and simulation results for IEEE test systems discussed. © 1991 IEEE.

Parallel dynamic graph-partitioning for unstructured meshes

A parallel method for the dynamic partitioning of unstructured meshes is described. The method introduces a new iterative optimisation technique known as relative gain optimisation which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Urheiluviestinnän murroksessa. Superpesis-seurojen sosiaalisen median käyttö

Urheiluseurojen viestintä on murroksen keskellä. Sosiaalisen median menestyksen myötä seuroista on tullut eräänlaisia omia uutistoimistojaan, joilta odotetaan ammattimaista ja ennen kaikkea nopeaa viestintää edustusjoukkueen ja sen pelaajien kuulumisista ja ottelutuloksista. Sosiaalinen media on myös itsessään muodostunut tärkeäksi tekijäksi urheiluseurojen viestinnän ja markkinoinnin tehokkuudessa sekä brändin muodostumisessa ja näkyvyydessä. Kaikilla urheiluseuroilla ei kuitenkaan ole tarvittavia resursseja menestyvän brändin luomiseksi sosiaalisen median kanavia käyttäen. Esimerkkinä tässä tutkimuksessa toimivat Superpesis-sarjan pesäpalloseurat, joiden sisältä miesten ja naisten sarjoista löytyy suuria eroavaisuuksia saatavilla olevissa resursseissa ja toteutetun viestinnän laadussa, mieleenpainuvuudessa ja tehokkuudessa. Tutkimukseni primaariaineistoina toimivat Superpesis-seuroille toteutettu sosiaalisen median käyttöä koskeva kyselyaineisto ja naisten Superpesis-seura Pesäkarhujen sosiaalisen median ja kotisivujen tilastot vuosilta 2013–2016. Kyselyyn vastasi 25 mahdollisesta Superpesis-seurasta 22 seuraa, joten vastaajajoukko on edustava kertomaan siitä, miten huipputason pesäpalloseurat tällä hetkellä viestivät. Saamieni tutkimustulosten perusteella listasin näille seuroille sosiaalisen median käytön suosituksia, joiden kautta seurojen on mahdollista kehittää viestintäänsä.

Urheiluviestinnän murroksessa. Superpesis-seurojen sosiaalisen median käyttö.

Urheiluseurojen viestintä on murroksen keskellä. Sosiaalisen median menestyksen myötä seuroista on tullut eräänlaisia omia uutistoimistojaan, joilta odotetaan ammattimaista ja ennen kaikkea nopeaa viestintää edustusjoukkueen ja sen pelaajien kuulumisista ja ottelutuloksista. Sosiaalinen media on myös itsessään muodostunut tärkeäksi tekijäksi urheiluseurojen viestinnän ja markkinoinnin tehokkuudessa sekä brändin muodostumisessa ja näkyvyydessä. Kaikilla urheiluseuroilla ei kuitenkaan ole tarvittavia resursseja menestyvän brändin luomiseksi sosiaalisen median kanavia käyttäen. Esimerkkinä tässä tutkimuksessa toimivat Superpesis-sarjan pesäpalloseurat, joiden sisältä miesten ja naisten sarjoista löytyy suuria eroavaisuuksia saatavilla olevissa resursseissa ja toteutetun viestinnän laadussa, mieleenpainuvuudessa ja tehokkuudessa. Tutkimukseni primaariaineistoina toimivat Superpesis-seuroille toteutettu sosiaalisen median käyttöä koskeva kyselyaineisto ja naisten Superpesis-seura Pesäkarhujen sosiaalisen median ja kotisivujen tilastot vuosilta 2013–2016. Kyselyyn vastasi 25 mahdollisesta Superpesis-seurasta 22 seuraa, joten vastaajajoukko on edustava kertomaan siitä, miten huipputason pesäpalloseurat tällä hetkellä viestivät. Saamieni tutkimustulosten perusteella listasin näille seuroille sosiaalisen median käytön suosituksia, joiden kautta seurojen on mahdollista kehittää viestintäänsä.

Probabilistic Models for Scalable Knowledge Graph Construction

In the past decade, systems that extract information from millions of Internet documents have become commonplace. Knowledge graphs -- structured knowledge bases that describe entities, their attributes and the relationships between them -- are a powerful tool for understanding and organizing this vast amount of information. However, a significant obstacle to knowledge graph construction is the unreliability of the extracted information, due to noise and ambiguity in the underlying data or errors made by the extraction system and the complexity of reasoning about the dependencies between these noisy extractions. My dissertation addresses these challenges by exploiting the interdependencies between facts to improve the quality of the knowledge graph in a scalable framework. I introduce a new approach called knowledge graph identification (KGI), which resolves the entities, attributes and relationships in the knowledge graph by incorporating uncertain extractions from multiple sources, entity co-references, and ontological constraints. I define a probability distribution over possible knowledge graphs and infer the most probable knowledge graph using a combination of probabilistic and logical reasoning. Such probabilistic models are frequently dismissed due to scalability concerns, but my implementation of KGI maintains tractable performance on large problems through the use of hinge-loss Markov random fields, which have a convex inference objective. This allows the inference of large knowledge graphs using 4M facts and 20M ground constraints in 2 hours. To further scale the solution, I develop a distributed approach to the KGI problem which runs in parallel across multiple machines, reducing inference time by 90%. Finally, I extend my model to the streaming setting, where a knowledge graph is continuously updated by incorporating newly extracted facts. I devise a general approach for approximately updating inference in convex probabilistic models, and quantify the approximation error by defining and bounding inference regret for online models. Together, my work retains the attractive features of probabilistic models while providing the scalability necessary for large-scale knowledge graph construction. These models have been applied on a number of real-world knowledge graph projects, including the NELL project at Carnegie Mellon and the Google Knowledge Graph.

A graph-based hyper heuristic for timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyperheuristic framework, a Tabu Search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the Tabu Search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.

Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems

This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyperheuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics for solving a problem. We developed a Tabu Search based hyper-heuristic to search for heuristic lists (of graph heuristics) for solving problems and investigated the heuristic lists found by employing knowledge discovery techniques. Two hybrid approaches (involving Saturation Degree and Largest Degree) including one which employs Case Based Reasoning are presented and discussed. Both the Tabu Search based hyper-heuristic and the hybrid approaches are tested on random and real-world exam timetabling problems. Experimental results are comparable with the best state-of-the-art approaches (as measured against established benchmark problems). The results also demonstrate an increased level of generality in our approach.

Case-based reasoning in course timetabling: an attribute graph approach

An earlier Case-based Reasoning (CBR) approach developed by the authors for educational course timetabling problems employed structured cases to represent the complex relationships between courses. Previous solved cases represented by attribute graphs were organized hierarchically into a decision tree. The retrieval searches for graph isomorphism among these attribute graphs. In this paper, the approach is further developed to solve a wider range of problems. We also attempt to retrieve those graphs that have common similar structures but also have some differences. Costs that are assigned to these differences have an input upon the similarity measure. A large number of experiments are performed consisting of different randomly produced timetabling problems and the results presented here strongly indicate that a CBR approach could provide a significant step forward in the development of automated system to solve difficult timetabling problems. They show that using relatively little effort, we can retrieve these structurally similar cases to provide high quality timetables for new timetabling problems.

A graph-based hyper heuristic for timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyperheuristic framework, a Tabu Search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the Tabu Search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.