The primary objective of this work is to utilize the GloVeNoR node embedding technique, as well as the Simplex2Vec triangle embedding technique, to perform higher-order link prediction, i.e., the possibility of an interaction of more than two nodes. Additionally, we evaluate the predictions generated by our methods and compare them with existing higher-order link prediction approaches using various benchmark datasets. Based on our experiments, we show that the triangle embeddings generated using our techniques increase the average performance over the five datasets evaluated using the AUC-PR relative to random baseline as a metric for higher-order link prediction.

We study the community detection problem by embedding the nodes of a graph into a n-dimensional space such that similar nodes remain close in their representations. There are many state-of-the-art methods, like node2vec and DeepWalk to compute node embeddings with the use of second order random walks. These techniques borrow methods like the Skip-Gram model, used in the domain of Natural Language Processing (NLP) to compute word embeddings. This paper explores the idea of porting the GloVe (Global Vectors for Word Representation) model, a popular technique for word embeddings, to a new method called GloVeNoR, to compute node embeddings in a graph, and creating a corpus with the use of second order random walks. We evaluate the model's quality by comparing it against node2vec and DeepWalk on the problem of community detection on five different data sets. We observe that GloVeNoR discovers similar or better communities than the other existing models on all the datasets based on the modularity score.

Higher-order structures, like triangles, in networks provide rich information about a network. Usually, the focus is on pairwise interactions that are modeled as edges. However, many interactions may actually involve more than two nodes simultaneously. For example, social interactions often occur in groups of people, research collaborations are among more than two authors, and biological networks describe interactions of a group of proteins. Predicting the occurrence of such higher-order structures helps us solve problems in various disciplines, such as social network analysis, drug combinations research, and news topic connections. The primary focus of this paper is to explore representations of three-node interactions, called triangles (a special case of higher-order structures) in order to predict higher-order links. We propose new methods to embed triangles by generalizing the node2vec algorithm under different operators, by using 1-hop subgraphs in the the graph2vec algorithm, and in graph neural networks. The performance of these techniques is evaluated against some benchmark scores on various datasets used in the bibliography. From the results, it is observed that our node2vec based triangle embedding method performs better or similar on most of the datasets compared to previous models.

Crime has been prevalent in our society for a very long time and it continues to be so even today. Currently, many cities have released crime-related data as part of an open data initiative. Using this as input, we can apply analytics to be able to predict and hopefully prevent crime in the future. In this work, we applied big data analytics to the San Francisco crime dataset, as collected by the San Francisco Police Department and available through the Open Data initiative. The main focus is to perform an in-depth analysis of the major types of crimes that occurred in the city, observe the trend over the years, and determine how various attributes contribute to specific crimes. Furthermore, we leverage the results of the exploratory data analysis to inform the data preprocessing process, prior to training various machine learning models for crime type prediction. More specifically, the model predicts the type of crime that will occur in each district of the city. We observe that the provided dataset is highly imbalanced, thus metrics used in previous research focus mainly on the majority class, disregarding the performance of the classifiers in minority classes, and propose a methodology to improve this issue. The proposed model finds applications in resource allocation of law enforcement in a Smart City.

During the last few decades the problem of community detection in social networks has become an important and challenging computational task. Consequently, a number of algorithms have been proposed in the relevant literature, some of which seem to solve the problem quite efficiently. The huge amount of data, however, forces for further improved techniques that can handle large and complicated networks. In this paper, we consider the effect of assigning weights on edges of unweighted network graphs and estimate their importance in community detection. In particular, we propose a new edge weight function and study its effect when used as a preprocessing step for community detection algorithms. Experimental results on a benchmark of random networks confirm our intuition that assigning weights on edges can play an important role in improving the performance of such algorithms.

We propose and investigate Selfish Path MultiColoring games as a natural model for noncooperative wavelength assignment in multifiber optical networks. In this setting, we view the wavelength assignment process as a strategic game in which each communication request selfishly chooses a wavelength in an effort to minimize the maximum congestion that it encounters on the chosen wavelength. We measure the cost of a certain wavelength assignment as the maximum, among all physical links, number of parallel fibers employed by this assignment. We start by settling questions related to the existence and computation of and convergence to pure Nash equilibria in these games. Our main contribution is a thorough analysis of the price of anarchy of such games, that is, the worst-case ratio between the cost of a Nash equilibrium and the optimal cost. We first provide upper bounds on the price of anarchy for games defined on general network topologies. Along the way, we obtain an upper bound of 2 for games defined on star networks. We next show that our bounds are tight even in the case of tree networks of maximum degree 3, leading to nonconstant price of anarchy for such topologies. In contrast, for network topologies of maximum degree 2, the quality of the solutions obtained by selfish wavelength assignment is much more satisfactory: We prove that the price of anarchy is bounded by 4 for a large class of practically interesting games defined on ring networks.

Abstract We are interested in the problem of satisfying a maximum‐profit subset of undirected communication requests in an optical ring that uses the Wavelength Division Multiplexing technology. We present four deterministic and purely combinatorial algorithms for this problem, and give theoretical guarantees for their worst‐case approximation ratios. Two of these algorithms are novel, whereas the rest are adaptation of earlier approaches. An experimental evaluation of the algorithms in terms of attained profit and execution time reveals that the theoretically best algorithm performs only marginally better than one of the new algorithms, while at the same time being several orders of magnitude slower. Furthermore, an extremely fast greedy heuristic with nonconstant approximation ratio performs reasonably well and may be favored over the other algorithms whenever it is crucial to minimize execution time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Boundary labeling is a relatively new labeling method. It can be useful in automating the production of technical drawings and medical maps, where it is common to explain certain parts of the drawing with text labels, arranged on its boundary so that other parts of the drawing are not obscured. In boundary labeling, we are given a rectangle R which encloses a set of n sites. Each site si is associated with an axis-parallel rectangular label li. The labels must be placed in distinct positions on the boundary of R and to be connected to their corresponding sites with polygonal lines, called leaders, so that the labels are pairwise disjoint and the leaders do not intersect each other. In this paper, we study a version of the boundary labeling problem where the sites can “float ” within a polygonal region. We present a polynomial time algorithm that produces a labeling of minimum total leader length for labels of uniform size placed in fixed positions on the boundary of R.