This thesis introduces an innovative methodology of combining some traditional dictionary based approaches to word sense disambiguation (semantic similarity measures and overlap of word glosses, both based on WordNet) with some graph-based centrality methods, namely the degree of the vertices, Pagerank, closeness, and betweenness. The approach is completely unsupervised, and is based on creating graphs for the words to be disambiguated. We experiment with several possible combinations of the semantic similarity measures as the first stage in our experiments. The next stage attempts to score individual vertices in the graphs previously created based on several graph connectivity measures. During the final stage, several voting schemes are applied on the results obtained from the different centrality algorithms. The most important contributions of this work are not only that it is a novel approach and it works well, but also that it has great potential in overcoming the new-knowledge-acquisition bottleneck which has apparently brought research in supervised WSD as an explicit application to a plateau. The type of research reported in this thesis, which does not require manually annotated data, holds promise of a lot of new and interesting things, and our work is one of the first steps, despite being a small one, in this direction. The complete system is built and tested on standard benchmarks, and is comparable with work done on graph-based word sense disambiguation as well as lexical chains. The evaluation indicates that the right combination of the above mentioned metrics can be used to develop an unsupervised disambiguation engine as powerful as the state-of-the-art in WSD.

abstract: Hyperbolic geometry, which is a geometry which concerns itself with hyperbolic space, has caught the eye of certain circles in the machine learning community as of late. Lauded for its ability to encapsulate strong clustering as well as latent hierarchies in complex and social networks, hyperbolic geometry has proven itself to be an enduring presence in the network science community throughout the 2010s, with no signs of fading into obscurity anytime soon. Hyperbolic embeddings, which map a given graph to hyperbolic space, have particularly proven to be a powerful and dynamic tool for studying complex networks. Hyperbolic embeddings are exploited in this thesis to illustrate centrality in a graph. In network science, centrality quantifies the influence of individual nodes in a graph. Eigenvector centrality is one type of such measure, and assigns an influence weight to each node in a graph by solving for an eigenvector equation. A procedure is defined to embed a given network in a model of hyperbolic space, known as the Poincare disk, according to the influence weights computed by three eigenvector centrality measures: the PageRank algorithm, the Hyperlink-Induced Topic Search (HITS) algorithm, and the Pinski-Narin algorithm. The resulting embeddings are shown to accurately and meaningfully reflect each node's influence and proximity to influential nodes. / Dissertation/Thesis / Masters Thesis Computer Science 2020

De nos jours, les interactions ont une part prépondérante dans notre vie. Ces interactions peuvent représenter la diffusion de rumeurs, de maladies, etc. Comprendre comment ces interactions affectent notre vie est important. Une façon naturelle de faire est d'utiliser la théorie des graphes. Néanmoins, comme le montrent certaines études, l'aspect temporel ne doit pas être négligé. Dans ce travail, nous nous sommes concentrés sur la détection d'individus importants dans ces graphes en utilisant des métriques de centralité qui prennent en compte l'aspect temporel. Nous avons proposé un protocole de comparaison qui compare les différentes mesures de centralité existantes. Nous l'avons appliqué sur plusieurs graphes, ce qui nous a donné un aperçu de la façon dont les différentes métriques agissent. Ensuite, nous avons observé le besoin de calcul élevé de ces métriques de centralité. Dès lors, nous avons introduit une méthode qui réduit ce besoin. Finalement, nous avons introduit une nouvelle mesure de centralité, appelée ego-betweenness centrality. / Nowadays, interactions are a huge part of our daily life. These interactions can represent the diffusion of rumors, diseases, etc. Understanding how these interactions affect our life is quite important. A natural way to do so is using graph theory. However, this is not straightforward as studies show the temporal aspect, in other words, the order of interactions, should be taken into account. In this work, we concentrated on detecting the important individuals in these graphs using centrality metrics that take into account the temporal aspect. We proposed a comparison protocol that compares the different centrality metrics that exist. We applied it on several networks, which gave us insight on how the different metrics react. Secondly, we observed the high computational need of these centrality metrics. Therefore, we introduced a method to reduce this need. And finally, we introduced a novel centrality metric that we call ego-betweenness centrality.

The central vertices in complex networks are of particular interest because they might play the role of organizational hubs. Here, we consider three different geometric centrality measures, excentricity, status, and centroid value, that were originally used in the context of resource placement problems. We show that these quantities lead to useful descriptions of the centers of biological networks which often, but not always, correlate with a purely local notion of centrality such as the vertex degree. We introduce the notion of local centers as local optima of a centrality value “landscape” on a network and discuss briefly their role.

In network analysis, it is useful to identify important vertices in a network. Based on the varying notions of importance of vertices, a number of centrality measures are defined and studied in the literature. Some popular centrality measures, such as betweenness centrality, are computationally prohibitive for large-scale networks. In this thesis, we propose a new centrality measure called k-path centrality and experimentally compare this measure with betweenness centrality. We present a polynomial-time randomized algorithm for distinguishing high k-path centrality vertices from low k-path centrality vertices in any given (unweighted or weighted) graph. Specifically, for any graph G = (V, E) with n vertices and for every choice of parameters α ∈ (0, 1), ε ∈ (0, 1/2), and integer k ∈ [1, n], with probability at least 1 − 1/n2 our randomized algorithm distinguishes all vertices v ∈ V that have k-path centrality Ck(v) more than nα(1 + 2ε) from all vertices v ∈ V that have k-path centrality Ck(v) less than nα(1 − 2ε). The running time of the algorithm is O(k2ε −2n1−α ln n). Theoretically and experimentally, our algorithms are (for suitable choices of parameters) significantly faster than the best known deterministic algorithm for computing exact betweenness centrality values (Brandes’ algorithm). Through experimentations on both real and randomly generated networks, we demonstrate that vertices that have high betweenness centrality values also have high k-path centrality values.

The need to understand the structure of complex networks increases as both their complexity and the dependency of human society on them grows. Network centralities help to recognize the key elements of these networks. Betweenness centrality is a network centrality measure based on shortest paths. More precisely, the contribution of a pair of vertices u, v to a vertex w ̸= u, v is the fraction of the shortest uv-paths which lead through w. Betweenness centrality is then given by the sum of contributions of all pairs of vertices u, v ̸= w to w. In this work, we have summarized known results regarding both exact values and bounds on betweenness. Additionally, we have improved an existing bound and obtained more exact formulation for r-regular graphs. We have made two major contributions about betweenness uniform graphs, whose vertices have uniform betweenness value. The first is that all betweenness uniform graphs of order n with maximal degree n − k have diameter at most k, by which we have solved a conjecture posed in the literature. The second major result is that betweenness uniform graphs nonisomorphic to a cycle that are either vertex- or edge-transitive are 3-connected, by which we have partially solved another conjecture. 1

No description available.

We investigate the applicability of network analysis to the problem of finding seminal publications in scientific publishing. In particular, we focus on the network measures betweenness centrality, the so-called backbone graph, and the burstiness of citations. The metrics are evaluated using precision-related scores with respect to gold standards based on fellow programmes and manual annotation. Citation counts, PageRank, and random selection are used as baselines. We find that the backbone graph provides us with a way to possibly discover seminal publications with low citation count, and combining betweenness and burstiness gives results on par with citation count. / I detta examensarbete undersöks det huruvida analys av citeringsgrafer kan användas för att finna betydelsefulla vetenskapliga publikationer. Framför allt studeras ”betweenness”-centralitet, den så kallade ”backbone”-grafen samt ”burstiness” av citeringar. Dessa mått utvärderas med hjälp av precisionsmått med avseende på guldstandarder baserade på ’fellow’-program samt via manuell annotering. Antal citeringar, PageRank, och slumpmässigt urval används som jämförelse. Resultaten visar att ”backbone”-grafen kan bidra till att eventuellt upptäcka betydelsefulla publikationer med ett lågt antal citeringar samt att en kombination av ”betweenness” och ”burstiness” ger resultat i nivå med de man får av att räkna antal citeringar.

The cognitive decline associated with healthy aging begins in early adulthood and is important to understand as a precursor of and relative to mild cognitive impairment and Alzheimer disease. Anatomical atrophy, functional compensation, and network reorganization have been observed in populations of older adults. In the current study, we examine functional network correlates of memory performance on the Wechsler Memory Scale IV and the Mnemonic Discrimination Task (MST). We report a lack of association between global graph theory metrics and age or memory performance. In addition, we observed a positive association between lure discrimination scores from the MST and right hippocampus centrality. Upon further investigation, we confirmed that old subjects with poor memory performance had lower right hippocampus centrality scores than young subjects with high average memory performance. These novel results connect the role of the hippocampus in global brain network information flow to cognitive function and have implications for better characterizing and predicting memory decline in aging.

Criminal networks exploit vulnerabilities in the global financial system, using it as a conduit to launder criminal proceeds. Law enforcement agencies, financial institutions, and regulatory organizations often scrutinize voluminous financial records for suspicious activities and criminal conduct as part of anti-money laundering investigations. However, such studies are narrowly focused on incidents and triggered by tip-offs rather than data mining insights. This research models cross-border financial flows using a network theoretic approach and proposes a symmetric-key encryption algorithm to preserve information privacy in multi-dimensional data sets. The newly developed tools will enable regulatory organizations, financial institutions, and law enforcement agencies to identify suspicious activity and criminal conduct in cross-border financial transactions. Anti-money laundering, which comprises laws, regulations, and procedures to combat money laundering, requires financial institutions to verify and identify their customers in various circumstances and monitor suspicious activity transactions. Instituting anti-money laundering laws and regulations in a country carries the benefit of creating a data-rich environment, thereby facilitating non-classical analytical strategies and tools. Graph theory offers an elegant way of representing cross-border payments/receipts between resident and non-resident parties (nodes), with links representing the parties' transactions. The network representations provide potent data mining tools, facilitating a better understanding of transactional patterns that may constitute suspicious transactions and criminal conduct. Using network science to analyze large and complex data sets to detect anomalies in the data set is fast becoming more important and exciting than merely learning about its structure. This research leverages advanced technology to construct and visualize the cross-border financial flows' network structure, using a directed and dual-weighted bipartite graph. Furthermore, the develops a centrality measure for the proposed cross-border financial flows network using a method based on matrix multiplication to answer the question, "Which resident/non-resident nodes are the most important in the cross-border financial flows network?" The answer to this question provides data mining insights about the network structure. The proposed network structure, centrality measure, and characterization using degree distributions can enable financial institutions and regulatory organizations to identify dominant nodes in complex multi-dimensional data sets. Most importantly, the results showed that the research provides transaction monitoring capabilities that allow the setting of customer segmentation criteria, complementing the built-in transaction-specific triggers methods for detecting suspicious activity transactions. / Thesis (PhD)--University of Pretoria, 2021. / Banking Sector Education and Training Authority (BANKSETA) / UP Postgraduate Bursary / Industrial and Systems Engineering / PhD / Unrestricted