A Note on the periodic orbits and topological entropy of graph maps

This paper deals with the relationship between the periodic orbits of continuous maps on graphs and the topological entropy of the map. We show that the topological entropy of a graph map can be approximated by the entropy of its periodic orbits

Applications of graph transformation in tools for domain-specific modeling languages

The use of domain-specific languages (DSLs) has been proposed as an approach to cost-e ectively develop families of software systems in a restricted application domain. Domain-specific languages in combination with the accumulated knowledge and experience of previous implementations, can in turn be used to generate new applications with unique sets of requirements. For this reason, DSLs are considered to be an important approach for software reuse. However, the toolset supporting a particular domain-specific language is also domain-specific and is per definition not reusable. Therefore, creating and maintaining a DSL requires additional resources that could be even larger than the savings associated with using them. As a solution, di erent tool frameworks have been proposed to simplify and reduce the cost of developments of DSLs. Developers of tool support for DSLs need to instantiate, customize or configure the framework for a particular DSL. There are di erent approaches for this. An approach is to use an application programming interface (API) and to extend the basic framework using an imperative programming language. An example of a tools which is based on this approach is Eclipse GEF. Another approach is to configure the framework using declarative languages that are independent of the underlying framework implementation. We believe this second approach can bring important benefits as this brings focus to specifying what should the tool be like instead of writing a program specifying how the tool achieves this functionality. In this thesis we explore this second approach. We use graph transformation as the basic approach to customize a domain-specific modeling (DSM) tool framework. The contributions of this thesis includes a comparison of di erent approaches for defining, representing and interchanging software modeling languages and models and a tool architecture for an open domain-specific modeling framework that e ciently integrates several model transformation components and visual editors. We also present several specific algorithms and tool components for DSM framework. These include an approach for graph query based on region operators and the star operator and an approach for reconciling models and diagrams after executing model transformation programs. We exemplify our approach with two case studies MICAS and EFCO. In these studies we show how our experimental modeling tool framework has been used to define tool environments for domain-specific languages.

Visual analytics for behavioral and niche market segmentation

Companies require information in order to gain an improved understanding of their customers. Data concerning customers, their interests and behavior are collected through different loyalty programs. The amount of data stored in company data bases has increased exponentially over the years and become difficult to handle. This research area is the subject of much current interest, not only in academia but also in practice, as is shown by several magazines and blogs that are covering topics on how to get to know your customers, Big Data, information visualization, and data warehousing. In this Ph.D. thesis, the Self-Organizing Map and two extensions of it – the Weighted Self-Organizing Map (WSOM) and the Self-Organizing Time Map (SOTM) – are used as data mining methods for extracting information from large amounts of customer data. The thesis focuses on how data mining methods can be used to model and analyze customer data in order to gain an overview of the customer base, as well as, for analyzing niche-markets. The thesis uses real world customer data to create models for customer profiling. Evaluation of the built models is performed by CRM experts from the retailing industry. The experts considered the information gained with help of the models to be valuable and useful for decision making and for making strategic planning for the future.

Capillary electrophoresis: Applicability and method validation for biorefinery analytics

Wood-based bioprocesses present one of the fields of interest with the most potential in the circular economy. Expanding the use of wood raw material in sustainable industrial processes is acknowledged on both a global and a regional scale. This thesis concerns the application of a capillary zone electrophoresis (CZE) method with the aim of monitoring wood-based bioprocesses. The range of detectable carbohydrate compounds is expanded to furfural and polydatin in aquatic matrices. The experimental portion has been conducted on a laboratory scale with samples imitating process samples. This thesis presents a novel strategy for the uncertainty evaluation via in-house validation. The focus of the work is on the uncertainty factors of the CZE method. The CZE equipment is sensitive to ambient conditions. Therefore, a proper validation is essential for robust application. This thesis introduces a tool for process monitoring of modern bioprocesses. As a result, it is concluded that the applied CZE method provides additional results to the analysed samples and that the profiling approach is suitable for detecting changes in process samples. The CZE method shows significant potential in process monitoring because of the capability of simultaneously detecting carbohydrate-related compound clusters. The clusters can be used as summary terms, indicating process variation and drift.

Analytics for the modified kraft pulps

Tämän diplomityön tavoitteena on kehittää sopiva analyyttinen menetelmä muokatun kraft-sellukuidun substituutioasteen (DS) kvantitatiivista määrittämistä varten. Muokkauksella tarkoitetaan tässä yhteydessä joko kovalenttisesti tai adsorption avulla tapahtuvaa molekyylin kiinnittymistä sellukuidun pinnalle. Työn kirjallisuusosuudessa käsitellään lyhyesti eri muokkaustapoja ja yhdisteitä joiden avulla voidaan saavuttaa haluttuja ominaisuuksia sellusta valmistetuille lopputuotteille. Lisäksi kirjallisuusosuudessa käydään läpi käyttötarkoitukseen soveltuvimpia suoria ja epäsuoria analyysimenetelmiä. Analyysimenetelmistä kaikkein lupaavimpia testattiin työn kokeellisessa osassa. Diplomityön kokeellisessa osassa keskityttiin kehittämään muokatulle sellulle kvantitatiivista menetelmää DS:n määrittämiseksi Fourier-muunnos infrapuna-vaimennettu kokonaisheijastus (FTIR-ATR) spektrometrillä. Kirjallisuuskatsauksessa ei löytynyt yhtään dokumentoitua tutkimusta, jossa FTIR-ATR menetelmää olisi käytetty muokatun sellukuidun kvantitatiiviseen tutkimukseen. Muiden analyysimenetelmien, kuten alkuaineanalyysin, termogravimetrisen analyysin (TGA) ja valomikroskopian avulla pyrittiin tuottamaan lisätietoa muokkauksesta. Kvantitatiivisen FTIR-ATR menetelmän kehitykseen käytetyt muokatut sellukuidut olivat selluloosa-asetaattia ja selluloosa betainaattia. Saatujen tulosten perusteella muokattujen sulfiitti- ja kraft sellukuitujen DS:n kvantitatiivinen määrittäminen on mahdollista FTIR-ATR menetelmällä. Vähäinen kalibrointipisteiden määrä vaikeutti tarkan analyysimenetelmän tekemistä. Kehitetyn menetelmän suurimpina ongelmina olivat kiinteiden näytteiden heterogeenisyys sekä mahdollisten epäpuhtauksien tunnistaminen. Jatkotutkimusten avulla kehitettyä menetelmää on kuitenkin mahdollista käyttää muokattujen sellukuitujen jatkuvaan analysointiin selluteollisuudessa.

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.

Automatic Inference of Graph Models for Complex Networks with Genetic Programming

Complex networks can arise naturally and spontaneously from all things that act as a part of a larger system. From the patterns of socialization between people to the way biological systems organize themselves, complex networks are ubiquitous, but are currently poorly understood. A number of algorithms, designed by humans, have been proposed to describe the organizational behaviour of real-world networks. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. The algorithms, called graph models, represent significant human effort. Deriving accurate graph models is non-trivial, time-intensive, challenging and may only yield useful results for very specific phenomena. An automated approach can greatly reduce the human effort required and if effective, provide a valuable tool for understanding the large decentralized systems of interrelated things around us. To the best of the author's knowledge this thesis proposes the first method for the automatic inference of graph models for complex networks with varied properties, with and without community structure. Furthermore, to the best of the author's knowledge it is the first application of genetic programming for the automatic inference of graph models. The system and methodology was tested against benchmark data, and was shown to be capable of reproducing close approximations to well-known algorithms designed by humans. Furthermore, when used to infer a model for real biological data the resulting model was more representative than models currently used in the literature.

Network Similarity Measures and Automatic Construction of Graph Models using Genetic Programming

A complex network is an abstract representation of an intricate system of interrelated elements where the patterns of connection hold significant meaning. One particular complex network is a social network whereby the vertices represent people and edges denote their daily interactions. Understanding social network dynamics can be vital to the mitigation of disease spread as these networks model the interactions, and thus avenues of spread, between individuals. To better understand complex networks, algorithms which generate graphs exhibiting observed properties of real-world networks, known as graph models, are often constructed. While various efforts to aid with the construction of graph models have been proposed using statistical and probabilistic methods, genetic programming (GP) has only recently been considered. However, determining that a graph model of a complex network accurately describes the target network(s) is not a trivial task as the graph models are often stochastic in nature and the notion of similarity is dependent upon the expected behavior of the network. This thesis examines a number of well-known network properties to determine which measures best allowed networks generated by different graph models, and thus the models themselves, to be distinguished. A proposed meta-analysis procedure was used to demonstrate how these network measures interact when used together as classifiers to determine network, and thus model, (dis)similarity. The analytical results form the basis of the fitness evaluation for a GP system used to automatically construct graph models for complex networks. The GP-based automatic inference system was used to reproduce existing, well-known graph models as well as a real-world network. Results indicated that the automatically inferred models exemplified functional similarity when compared to their respective target networks. This approach also showed promise when used to infer a model for a mammalian brain network.

Object-Oriented Genetic Programming for the Automatic Inference of Graph Models for Complex Networks

Complex networks are systems of entities that are interconnected through meaningful relationships. The result of the relations between entities forms a structure that has a statistical complexity that is not formed by random chance. In the study of complex networks, many graph models have been proposed to model the behaviours observed. However, constructing graph models manually is tedious and problematic. Many of the models proposed in the literature have been cited as having inaccuracies with respect to the complex networks they represent. However, recently, an approach that automates the inference of graph models was proposed by Bailey [10] The proposed methodology employs genetic programming (GP) to produce graph models that approximate various properties of an exemplary graph of a targeted complex network. However, there is a great deal already known about complex networks, in general, and often specific knowledge is held about the network being modelled. The knowledge, albeit incomplete, is important in constructing a graph model. However it is difficult to incorporate such knowledge using existing GP techniques. Thus, this thesis proposes a novel GP system which can incorporate incomplete expert knowledge that assists in the evolution of a graph model. Inspired by existing graph models, an abstract graph model was developed to serve as an embryo for inferring graph models of some complex networks. The GP system and abstract model were used to reproduce well-known graph models. The results indicated that the system was able to evolve models that produced networks that had structural similarities to the networks generated by the respective target models.

Using Google Analytics to evaluate an email information literacy program for medical and dental students

Objectives: An email information literacy program has been effective for over a decade at Université de Montréal’s Health Library. Students periodically receive messages highlighting the content of guides on the library’s website. We wish to evaluate, using Google Analytics, the effects of the program on specific webpage statistics. Using the data collected, we may pinpoint popular guides as well as others that need improvement. Methods: In the program, first and second-year medical (MD) or dental (DMD) students receive eight bi-monthly email messages. The DMD mailing list also includes graduate students and professors. Enrollment to the program is optional for MDs, but mandatory for DMDs. Google Analytics (GA) profiles have been configured for the libraries websites to collect visitor statistics since June 2009. The GA Links Builder was used to design unique links specifically associated with the originating emails. This approach allowed us to gather information on guide usage, such as the visitor’s program of study, duration of page viewing, number of pages viewed per visit, as well as browsing data. We also followed the evolution of clicks on GA unique links over time, as we believed that users may keep the library's emails and refer to them to access specific information. Results: The proportion of students who actually clicked the email links was, on average, less than 5%. MD and DMD students behaved differently regarding guide views, number of pages visited and length of time on the site. The CINAHL guide was the most visited for DMD students whereas MD students consulted the Pharmaceutical information guide most often. We noted that some students visited referred guides several weeks after receiving messages, thus keeping them for future reference; browsing to additional pages on the library website was also frequent. Conclusion: The mitigated success of the program prompted us to directly survey students on the format, frequency and usefulness of messages. The information gathered from GA links as well as from the survey will allow us to redesign our web content and modify our email information literacy program so that messages are more attractive, timely and useful for students.

A Note On Some Domination Parameters in Graph Products

In this paper, we study the domination number, the global dom ination number, the cographic domination number, the global co graphic domination number and the independent domination number of all the graph products which are non-complete extended p-sums (NEPS) of two graphs.

The P3 Intersection Graph

We define a new graph operator called the P3 intersection graph, P3(G)- the intersection graph of all induced 3-paths in G. A characterization of graphs G for which P-3 (G) is bipartite is given . Forbidden subgraph characterization for P3 (G) having properties of being chordal , H-free, complete are also obtained . For integers a and b with a > 1 and b > a - 1, it is shown that there exists a graph G such that X(G) = a, X(P3( G)) = b, where X is the chromatic number of G. For the domination number -y(G), we construct graphs G such that -y(G) = a and -y (P3(G)) = b for any two positive numbers a > 1 and b. Similar construction for the independence number and radius, diameter relations are also discussed.

The Edge C4 Graph of a Graph

Abstract. The edge C4 graph E4(G) of a graph G has all the edges of Gas its vertices, two vertices in E4(G) are adjacent if their corresponding edges in G are either incident or are opposite edges of some C4. In this paper, characterizations for E4(G) being connected, complete, bipartite, tree etc are given. We have also proved that E4(G) has no forbidden subgraph characterization. Some dynamical behaviour such as convergence, mortality and touching number are also studied

GALLAI AND ANTI-GALLAI GRAPHS OF A GRAPH

Abstract. The paper deals with graph operators-the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H-free for any finite graph H. The case of complement reducible graphs-cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.