Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.

Cross sections of Lyons Creek from Cooks Mills Dam to culvert

Cross sections of Lyons Creek from Cooks Mills Dam to culvert (9 pages of charts, graphs and text, handwritten). This is signed by Fred Holmes, May 1857.

Properties and algorithms of the (n, k)-star graphs

The (n, k)-star interconnection network was proposed in 1995 as an attractive alternative to the n-star topology in parallel computation. The (n, k )-star has significant advantages over the n-star which itself was proposed as an attractive alternative to the popular hypercube. The major advantage of the (n, k )-star network is its scalability, which makes it more flexible than the n-star as an interconnection network. In this thesis, we will focus on finding graph theoretical properties of the (n, k )-star as well as developing parallel algorithms that run on this network. The basic topological properties of the (n, k )-star are first studied. These are useful since they can be used to develop efficient algorithms on this network. We then study the (n, k )-star network from algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms for basic communication, prefix computation, and sorting, etc. A literature review of the state-of-the-art in relation to the (n, k )-star network as well as some open problems in this area are also provided.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

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.

Rings, Group Rings, and Their Graphs

We associate some graphs to a ring R and we investigate the interplay between the ring-theoretic properties of R and the graph-theoretic properties of the graphs associated to R. Let Z(R) be the set of zero-divisors of R. We define an undirected graph ᴦ(R) with nonzero zero-divisors as vertices and distinct vertices x and y are adjacent if xy=0 or yx=0. We investigate the Isomorphism Problem for zero-divisor graphs of group rings RG. Let Sk denote the sphere with k handles, where k is a non-negative integer, that is, Sk is an oriented surface of genus k. The genus of a graph is the minimal integer n such that the graph can be embedded in Sn. The annihilating-ideal graph of R is defined as the graph AG(R) with the set of ideals with nonzero annihilators as vertex such that two distinct vertices I and J are adjacent if IJ=(0). We characterize Artinian rings whose annihilating-ideal graphs have finite genus. Finally, we extend the definition of the annihilating-ideal graph to non-commutative rings.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Diagrams (charts and graphs) made into a booklet with a newspaper cover

Diagrams (charts and graphs) made into a booklet with a newspaper cover. This booklet contains cross sections of the back ditch on the south side of the Welland Canal feeder, west of the Marshville culverts (45 pages, hand drawn). This was created by Fred Holmes, Oct. 3, 1857.

Charts and graphs of cross sections from Brown’s ditch culvert to the main drain

Charts and graphs of cross sections from Brown’s ditch culvert to the main drain, cross sections from the feeder on the road allowance between lots 26 and 27 in the 5th concession of Humberstone, Cross sections of the main drain from Lyons Creek culvert to the road allowance between lots 7 and 8 in Wainfleet and cross selections of the old ditch on the west side of the road allowance between lots 17 and 18 in the 3rd concession in Wainfleet (8 pages, hand drawn), n.d.

An exploration of gifted and highly able adolescents' experiences with stress and coping /

This narrative case study explored gifted and highly able adolescents' experiences with stress and coping. Nine students, ages 13-18, at 2 independent schools in southern Ontario, participated. They completed the Adolescent Coping Scale (Frydenberg & Lewis, 1993), and I generated individualized graphs of coping strategies. Participants talked about experiences they perceived as stressful in their academic, personal, social, and familial settings during a 60-90 minute one-on-one audiotaped interview. During the interview, each participant made observations about their own coping strategies profile. The interview was analyzed to identify stressor and coping themes. Participants completed a writing or art task to record perceptions of stress and coping. The 3 data sources were used to craft 9 individual story portraits, from which 5 main stressor themes emerged: issues of time; relationships, emotions, and communication; ethical, moral, and spiritual issues; global issues; and silences, or stressors not talked about in depth. Coping themes were: seeking relaxing activities; having positive attitudes and making wise choices; maintaining relationships with peers and family; understanding the role of faith and moral beliefs; having a supportive environment; knowing your own personality type; being aware of negative coping strategies; and keeping busy and avoiding stressfiil issues. The narratives are important because they present teenagers talking about their socioemotional worlds. The present findings provide empirical groundwork for curriculum development in affective education and highlight the importance of socioemotional development for future research in the area of giftedness and adolescence.

The sedimentology of unconsolidated deltaic and aeolian sediments east of Dunnville, Ontario /

Surficial sediments east of Dunnville, Ontario representing a limited deltaic/lacustrine/aeolian system are investigated with the aim of defining and interpreting their geological history by means of exarrrrning their sedimentology and interrelationships. The Folk and \oJard grain size statistics of samples fran the area were calculated. These sample parameters were e1en plotted on maps to detennine regional patterns. The strongest pattern observed was one of distinct fining to the east, away fran the sand source. Aeolian deposits were fourrl to be better sorted than the surrcunding sediments. The grain size parameter values were also plotted on bivariate graphs in an attempt to separate the samples according to depositional environment. This exercise met with little success, as rrost of the sediments sampled in the area have similar grain size parameters. This is believed to be because the sediment sources for the different environments (delta, distal delta, aeolian dune) are intimately related, to the point that nnst dunes appear to have been sourcErl fran immediately local sediments. It is FOstulated that in such a srrall sedimentological sub-system, sediments were not involved in active transport for a length of time sufficient for the rraterial to cane to equilibritnn with its transporting medium. Thus, fe..v distinctive patterns of parameters were developed that would enable one to differentiate between various environments of neposition. The i.rnTaturity of rrany dune forms and the i.Imaturity of mineralogical composition of all deposits support the above hyt:XJthesis of limited transport time. Another hypothesis proposen is that eadh geologically or geographically distinct area or "sub-system" rray have its o,.m "signature" of grain size relationships as plotted on bivariate graphs. Thus, the emphasis, concerning graphs of this type, should not be placErl on attempting to nifferentiate between various environnents of deposition, hut raB1er on investigating the interrelationships between sanples am environments within that "sub-system". Through the course of this investigation, the existence of nelta plain distributary Channels in the thesis area is SUG0ested, and the mscovery of significantly mfferent sub-units within the TUnnville dune sediments is documented. It is inferred by reference to other authors interpretations of the glacial history of the area, that the tirre of effective aeolian acti vi ty in the Dunnville area was between 12,300 to 12,100 years R.p.

Square Root Finding In Graphs

Abstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NP-complete. This result is providing the complete dichotomy theorem for square root finding problem.

Acyclic 5-Choosability of Planar Graphs Without Adjacent Short Cycles

The conjecture claiming that every planar graph is acyclic 5-choosable[Borodin et al., 2002] has been verified for several restricted classes of planargraphs. Recently, O. V. Borodin and A. O. Ivanova, [Journal of Graph Theory,68(2), October 2011, 169-176], have shown that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3<=j<=5 if i=3 and 4<=j<=6 if i=4. We improve the above mentioned result and prove that every planar graph without an i-cycle adjacent to a j-cycle with3<=j<=5 if i=3 and 4<=j<=5 if i=4 is acyclically 5-choosable.

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.

Backbone Colouring of Graphs

Consider an undirected graph G and a subgraph of G, H. A q-backbone k-colouring of (G,H) is a mapping f: V(G) {1, 2, ..., k} such that G is properly coloured and for each edge of H, the colours of its endpoints differ by at least q. The minimum number k for which there is a backbone k-colouring of (G,H) is the backbone chromatic number, BBCq(G,H). It has been proved that backbone k-colouring of (G,T) is at most 4 if G is a connected C4-free planar graph or non-bipartite C5-free planar graph or Cj-free, j∈{6,7,8} planar graph without adjacent triangles. In this thesis we improve the results mentioned above and prove that 2-backbone k-colouring of any connected planar graphs without adjacent triangles is at most 4 by using a discharging method. In the second part of this thesis we further improve these results by proving that for any graph G with χ(G) ≥ 4, BBC(G,T) = χ(G). In fact, we prove the stronger result that a backbone tree T in G exists, such that ∀ uv ∈ T, |f(u)-f(v)|=2 or |f(u)-f(v)| ≥ k-2, k = χ(G). For the case that G is a planar graph, according to Four Colour Theorem, χ(G) = 4; so, BBC(G,T) = 4.