This paper presents a new graph-based approach that induces synsets using synonymy dictionaries and word embeddings. First, we build a weighted graph of synonyms extracted from commonly available resources, such as Wiktionary. Second, we apply word sense induction to deal with ambiguous words. Finally, we cluster the disambiguated version of the ambiguous input graph into synsets. Our meta-clustering approach lets us use an efficient hard clustering algorithm to perform a fuzzy clustering of the graph. Despite its simplicity, our approach shows excellent results, outperforming five competitive state-of-the-art methods in terms of F-score on three gold standard datasets for English and Russian derived from large-scale manually constructed lexical resources.
(CW) @cite_11 is a clustering algorithm for weighted graphs that can be considered as a special case of MCL with a simplified class update step. At each iteration, the labels of all the nodes are updated according to the majority labels among the neighboring nodes. The algorithm has a meta-parameter that controls graph weights that can be set to three values: (1) sums over the neighborhood's classes; (2) downgrades the influence of a neighboring node by its degree or by (3) of its degree.
@cite_11
1987302197
Given a network of interconnected nodes, each with a given initial value, we develop a distributed strategy that enables some or all of the nodes to calculate any arbitrary function of these initial values, despite the presence of some malicious (or faulty) nodes. Our scheme utilizes a linear iterative strategy where, at each time-step, each node updates its value to be a weighted average of its own previous value and those of its neighbors. We consider a node to be malicious if, instead of following the predefined linear iterative strategy, it updates its value arbitrarily at each time-step (perhaps by conspiring and coordinating with other malicious nodes). When there are up to f malicious nodes, we show that any node in the network is guaranteed to be able to calculate any arbitrary function of all initial node values if the graph of the network is at least (2f +1)-connected. Specifically, we show that under this condition, the nodes can calculate their desired functions after running the linear iteration for a finite number of time- steps (upper bounded by the number of nodes in the network) using almost any set of weights (i.e., for all weights except for a set of measure zero). Our approach treats the problem of fault-tolerant distributed consensus, where all nodes have to calculate the same function despite the presence of faulty or malicious nodes, as a special case. Distributed averaging describes a class of network algorithms for the decentralized computation of aggregate statistics. Initially, each node has a scalar data value, and the goal is to compute the average of these values at every node (the so-called average consensus problem). Nodes iteratively exchange information with their neighbors and perform local updates until the value at every node converges to the initial network average. Much previous work has focused on algorithms where each node maintains and updates a single value; every time an update is performed, the previous value is forgotten. Convergence to the average consensus is achieved asymptotically. The convergence rate is fundamentally limited by network connectivity, and it can be prohibitively slow on topologies such as grids and random geometric graphs, even if the update rules are optimized. In this paper, we provide the first theoretical demonstration that adding a local prediction component to the update rule can significantly improve the convergence rate of distributed averaging algorithms. We focus on the case where the local predictor is a linear combination of the node's current and previous values (i.e., two memory taps), and our update rule computes a combination of the predictor and the usual weighted linear combination of values received from neighboring nodes. We derive the optimal mixing parameter for combining the predictor with the neighbors' values, and conduct a theoretical analysis of the improvement in convergence rate that can be achieved using this acceleration methodology. For a chain topology on N nodes, this leads to a factor of N improvement over standard consensus, and for a two-dimensional grid, our approach achieves a factor of ?N improvement. Given any fixed non-negative integer values h and k, the L(h, k)-labelling problem consists in an assignment of non-negative integers to the nodes of a graph such that adjacent nodes receive values which differ by at least h, and nodes connected by a 2-length path receive values which differ by at least k. The span of an L(h, k)-labelling is the difference between the largest and the smallest assigned frequency. The goal of the problem is to find out an L(h, k)-labelling with a minimum span. The L(h, k)-labelling problem has intensively been studied following many approaches and restricted to many special cases, concerning both the values of h and k and the considered classes of graphs. This paper reviews the results from previously published literature, looking at the problem with a graph algorithmic approach. It is an update of a previous survey written by the same author. We introduce and study the reverse voter model, a dynamics for spin variables similar to the well‐known voter dynamics. The difference is in the way neighbors influence each other: once a node is selected and one among its neighbors chosen, the neighbor is made equal to the selected node, while in the usual voter dynamics the update goes in the opposite direction. The reverse voter dynamics is studied analytically, showing that on networks with degree distribution decaying as k−v, the time to reach consensus is linear in the system size N for all v > 2. The consensus time for link‐update voter dynamics is computed as well. We verify the results numerically on a class of uncorrelated scale‐free graphs.