Community detections for large-scale real world networks have been more popular in social analytics. In particular, dynamically growing network analyses become important to find long-term trends and detect anomalies. In order to analyze such networks, we need to obtain many snapshots and apply same analytic methods to them. However, it is inefficient to extract communities from these whole newly generated networks with little differences every time, and then it is impossible to follow the network growths in the real time. We proposed an incremental community detection algorithm for high-volume graph streams. It is based on the top of a well-known batch-oriented algorithm named DEMON [1]. We also evaluated performance and precisions of our proposed incremental algorithm with real-world big networks with up to 410,236 vertices and 2,439,437 edges and computed in less than one second to detect communities in an incremental fashion — which achieves up to 107 times faster than the original algorithm without sacrificing accuracies.
Sheng et. al. focused an incremental label propagation algorithm and added the time sequences as well as labels to vertices @cite_6 . The average computation complexity was the same as the total number of local edges connected to the local vertices @math (m: the number of edges), and the worst case of the overall time was @math (n: the number of vertices). They showed that the average iteration time was 4.411 seconds with on-line game players networks. In this algorithm, additional tag data were necessary and the final results of network division might change with the number of iterations. Our proposed method considers only network structures, and output results are stable.
@cite_6
2167460951 2082227928 2049706966 2418286382
Most networks will evolve with time instead of keeping unchanged in reality. Therefore, we proposed the incremental label propagation (ILP) algorithm to detect community structures in complex networks in realtime. ILP algorithm will only take the local changed vertexes into consideration. The computation time is greatly decreased, while vertex (edge) is changed. The algorithm will definitely converge for the original version of label propagation algorithm is converged. We also applied ILP to real-time community detection in a relationship network of online game. We present a probabilistic algorithm that, given a connected graph G (represented by adjacency lists) of average degree d, with edge weights in the set 1,...,w , and given a parameter @math , estimates in time @math the weight of the minimum spanning tree (MST) of G with a relative error of at most @math . Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of @math on the probe and time complexity of any approximation algorithm for MST weight. The essential component of our algorithm is a procedure for estimating in time @math the number of connected components of an unweighted graph to within an additive error of @math . (This becomes @math for @math .) The time bound is shown to be tight up to within the @math factor. Our connected-components algorithm picks @math vertices in the graph and then grows "local spanning trees" whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST. An edge-scheduled network N is a multigraph G = (V, E), where each edge e ϵ E has been assigned two real weights: a start time α(e) and a finish time β(e). Such a multigraph models a communication or transportation network. A multiedge joining vertices u and v represents a direct communication (transportation) link between u and v, and the edges of the multiedge represent potential communications (transportations) between u and v over a fixed period of time. For a, b ϵ V, and k a nonnegative integer, we say that N is k-failure ab-invulnerable for the time period [0, t] if information can be relayed from a to b within that time period, even if up to k edges are deleted, i.e., “fail.” The k-failure ab-vulnerability threshold νab(k) is the earliest time t such that N is k-failure ab-invulnerable for the time period [0, t] [where νab(k) = ∞ if no such t exists]. Let κ denote the smallest k such that νab(k) = ∞. In this paper, we present an O(κ|E|) algorithm for computing νab(i), i = 0, …, κ −1. The latter algorithm constructs a set of κ pairwise edge-disjoint schedule-conforming paths P0, …, Pκ −1 such that the finish time of Pi is νab(i), i = 0, 1, …, κ −1. (A path P = ae1u1e2 ··· Upp−1epb is schedule-conforming if the finish time of edge ei is no greater than the start time of the next edge ei + 1.) The existence of such paths when α(e) = β(e) = 0, for all e ϵ E, implies Menger's Theorem. In this paper, we also show that the obvious analogs of these results for either multiedge deletions or vertex deletions do not hold. In fact, we show that the problem of finding k schedule-conforming paths such that no two paths pass through the same vertex (multiedge) is NP-complete, even for k = 2. © 1996 John Wiley & Sons, Inc. In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem with only O(mn) total update time over all edge deletions. Their classic algorithm was the best known result for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. The first improvement over the Even-Shiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented an approximate (1+) algorithm with constant query time and a total update time of O(n2+O(1 √logn)). This work triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a -approximate algorithm whose total update time is near linear O(m1+ O(1 √logn)). In this paper they posed as a major open problem the question of derandomizing their result. In fact, all known improvements over the Even-Shiloach algorithm are randomized. All these algorithms maintain some truncated shortest path trees from a small subset of nodes. While in the randomized setting it is possible to “hide” these nodes from the adversary, in the deterministic setting this is impossible: the adversary can delete all edges touching these nodes, thus forcing the algorithm to choose a new set of nodes and incur a new computation of shortest paths. In this paper we present the first deterministic decremental SSSP algorithm that breaks the Even-Shiloach bound of O(mn) total update time, for unweighted and undirected graphs. Our algorithm is (1 + є) approximate and achieves a total update time of O(n2). Our algorithm can also achieve the same bounds in the incremental setting. It is worth mentioning that for dense instances where m = Ω(n2 − 1 √log(n)), our algorithm is also faster than all existing randomized algorithms.