Political conversations have become a ubiquitous part of social media. When users interact and engage in discussions, there are usually two mediums available to them;textual conversations and platform-specific interac...
详细信息
Political conversations have become a ubiquitous part of social media. When users interact and engage in discussions, there are usually two mediums available to them;textual conversations and platform-specific interactions such as like, share (Facebook) or retweet (Twitter). Major social media platforms do not facilitate users with negative interaction options. However, many political network analysis tasks rely on not only positive but also negative linkages. Thus, detecting implicit negative links is an important and a challenging task. In this work, we propose an unsupervised framework utilising positive interactions, sentiment cues, and socially balanced triads for detecting implicit negative links. We also present an online variant of it for streaming data tasks. We show the effectiveness of both frameworks with experiments on two annotated datasets of politician Twitter accounts. Our experiments show that the proposed frameworks outperform other well-known and proposed baselines. To illustrate the detected implicit negative links' contribution, we compare the community detection accuracies using unsigned and signed networks. Experimental results using detected negative links show superiority on the three datasets where the camps are known a priori. We also present qualitative evaluations of polarisation patterns between communities which are only possible in the presence of negative links.
Pointer analysis is at the heart of most interprocedural program analyses. However, scaling pointer analysis to large programs is extremely challenging. In this article, we study incremental pointer analysis and prese...
详细信息
Pointer analysis is at the heart of most interprocedural program analyses. However, scaling pointer analysis to large programs is extremely challenging. In this article, we study incremental pointer analysis and present a new algorithm for computing the points-to information incrementally (i.e., upon code insertion, deletion, and modification). Underpinned by new observations of incremental pointer analysis, our algorithm significantly advances the state of the art in that it avoids redundant computations and the expensive graph reachability analysis, and preserves precision as the corresponding whole program exhaustive analysis. Moreover, it is parallel within each iteration of fixed-point computation. We have implemented our algorithm, IPA, for Java based on the WALA framework and evaluated its performance extensively on real-world large, complex applications. Experimental results show that IPA achieves more than 200X speedups over existing incremental algorithms, two to five orders of magnitude faster than whole program pointer analysis, and also improves the performance of an incremental data race detector by orders of magnitude. Our IPA implementation is open source and has been adopted by WALA.
This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with n vertices and m edges while su...
详细信息
ISBN:
(纸本)9781450357999
This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with n vertices and m edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using O(jt) processors and O(log n) worst-case update time, for a total of ONT. log n) work. This improves on the work of Ferragina [IPPS 1995] which costs O(log n) worst-case update time and 0(n213 log);171) work.
A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in 0(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic grap...
详细信息
ISBN:
(纸本)9781450355599
A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in 0(m) time after each update. But can it be maintained in time sublinear in m in fully dynamicgraphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O(min{Delta, m(3/4)}), where A is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O(min{A Delta, m(3/4)}) amortized message complexity, and O(1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC'16) that required an assumption of a non-adaptive oblivious adversary.
In this work, we study the problem of dispersion of mobile robots on dynamic rings. The problem of dispersion of n robots on an n node graph, introduced by Augustine and Moses Jr. [2], requires robots to coordinate wi...
详细信息
ISBN:
(纸本)9781450363723
In this work, we study the problem of dispersion of mobile robots on dynamic rings. The problem of dispersion of n robots on an n node graph, introduced by Augustine and Moses Jr. [2], requires robots to coordinate with each other and reach a configuration where exactly one robot is present on each node. This problem has real world applications and applies whenever we want to minimize the total cost of n agents sharing n resources, located at various places, subject to the constraint that cost of an agent moving to a different resource is comparatively much smaller than cost of multiple agents sharing a resource (e.g. smart electric cars sharing recharge stations). Study of this problem also provides indirect benefits to the studies of scattering on graphs, exploration by mobile robots, and load balancing on graphs. We solve the problem of dispersion in presence of two types of dynamism in the underlying graph: (i) vertex permutation and (ii) 1-interval connectivity. We introduce the notion of vertex permutation dynamism and have it mean that for a given set of nodes, in every round, the adversary ensures a ring structure is maintained, but the connections between the nodes may change. We use the idea of 1-interval connectivity from Di Luna et al. [11], where for a given ring, in each round, the adversary chooses at most one edge to remove. We assume robots have full visibility and present asymptotically time optimal algorithms to achieve dispersion in the presence of both types of dynamism when robots have chirality. When robots do not have chirality, we present asymptotically time optimal algorithms to achieve dispersion subject to certain constraints. Finally, we provide impossibility results for dispersion when robots have no visibility.
We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(n(o(1))) worst-case update time with hig...
详细信息
ISBN:
(纸本)9781538634646
We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(n(o(1))) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen [2] with update time O(n(0.5-epsilon)) for some constant epsilon > 0 and, independently, by Nanongkai and Saranurak [3] with update time O(n(0.494)) (the latter works only for maintaining a spanning forest). Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n(0.5-epsilon)) in [2] to O(n(o(1))) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the "contraction technique" by Henzinger and King [4] and Holm et al. [5], we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1 + o(1))n) edges. This significantly improves the previous approach in [2], [3] which is based on Frederickson's 2-dimensional topology tree [6] and illustrates a new application to this old technique.
We initiate the study of fast dynamicalgorithms for graph sparsification problems and obtain fully dynamicalgorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each updat...
详细信息
ISBN:
(纸本)9781509039333
We initiate the study of fast dynamicalgorithms for graph sparsification problems and obtain fully dynamicalgorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a (1 +/-epsilon)-spectral sparsifier with amortized update time poly(log n, epsilon(-1)). Second, we give a fully dynamic algorithm for maintaining a (1 +/-epsilon)-cut sparsifier with worst-case update time poly(log n, epsilon(-1)). Both sparsifiers have size n. poly(log n, epsilon(-1)). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a (1 - epsilon)-approximation to the value of the maximum flow in an unweighted, undirected, bipartite graph with amortized update time poly(log n, epsilon(-1)).
We study dynamic (1 + epsilon)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomiz...
详细信息
We study dynamic (1 + epsilon)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of (O) over tilde (mn/epsilon) and constant query time by Roditty and Zwick [SIAM J. Comput., 41 (2012), pp. 670-683]. The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [J. ACM, 28 (1981), pp. 1-4];it has a total update time of O(mn(2)) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of (O) over tilde (n(5/2)/epsilon) and constant query time that has an additive error of 2 in addition to the 1 + epsilon multiplicative error. This beats the previous (O) over tilde (mn/epsilon) time when m = Omega(n(3/2)). Note that the additive error is unavoidable since, even in the static case, an O(n(3-delta))-time (a so-called truly subcubic) combinatorial algorithm with 1 + epsilon multiplicative error cannot have an additive error less than 2 - epsilon, unless we make a major breakthrough for Boolean matrix multiplication [D. Dor, S. Halrepin, and U. Zwick, SIAM J. Comput., 29 (2000), pp. 1740-1759] and many other long-standing problems [V. Vassilevska Williams and R. Williams, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 645-654]. The algorithm can also be turned into a (2 + epsilon)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + epsilon)-approximation algorithm with (O) over tilde (n(5/2+O(root log(1/epsilon)/log n))) running time of Bernstein and Roditty [Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete algorithms, 2011, pp. 1355-1365] in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of (O) over tilde (mn/epsilon) and a query time
We present two deterministic dynamicalgorithms for the maximum matching problem. (1) An algorithm that maintains a (2 + epsilon)-approximate maximum matching in general graphs with O (poly(log n, 1/epsilon) update ti...
详细信息
ISBN:
(纸本)9781450341325
We present two deterministic dynamicalgorithms for the maximum matching problem. (1) An algorithm that maintains a (2 + epsilon)-approximate maximum matching in general graphs with O (poly(log n, 1/epsilon) update time. (2) An algorithm that maintains an al( approximation of the value of the maximum matching with 0(n(2)/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1 <= alpha(K) < 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(log n)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOGS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was 0(m(1/4)) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.
While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this i...
详细信息
ISBN:
(纸本)9781450335362
While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge. Given an input graph, the densest subgraph is the sub graph that maximizes the ratio between the number of edges and the number of nodes. For any > 0, our algorithm can, with high probability, maintain a (4 + 0-approximate solution under edge insertions and deletions using 0(n) space and 6(1) amortized time per update;here, n is the number of nodes in the graph and O hides the 0(poly n) term. The approximation ratio can be improved to (2 + 6) with more time. It can be extended to a (2 + 0-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in one pass. Prior to this, no algorithm could do so even in the special case of an incremental stream and even when there is no time restriction. The previously best algorithm in this setting required 0(log n) passes [6]. The space required by our algorithm is tight up to a polylogarithmic factor.
暂无评论