Overlapped community detection in social networks has become an important research area with the increasing popularity and complexity of the networks. Most of the existing solutions are either centralized or parallel ...
详细信息
ISBN:
(数字)9781728191270
ISBN:
(纸本)9781728191287
Overlapped community detection in social networks has become an important research area with the increasing popularity and complexity of the networks. Most of the existing solutions are either centralized or parallel algorithms, which are computationally intensive - require complete knowledge of the entire network. But it isn't easy to collect entire network data because the size of the actual network may be prohibitively large. It may result from either privacy concerns (users of a social network may be unwilling to reveal their social links) or technological impediments (implementation of an efficient web crawler). Performing in-network computation solves both problems utilizing the computational capability of the individual nodes of the network. Simultaneously, nodes communicate and share data with their neighbours via message passing, which may go a long way toward mitigating individual nodes' privacy concerns in the network. All the concerns mentioned above motivated us to design a decentralized or distributed technique to detect overlapped communities in a large-scale network. It is desirable because this technique does not offer a single point of failure, and the system as a whole can continue to function even when many of the nodes fail. To overcome the disadvantages of the existing solutions, in this paper, we address the overlapped community detection problem for large-scale networks. We present an efficient distributed algorithm, named DOCD, to identify the overlapped communities in the network. The efficiency of DOCD algorithm is verified with extensive simulation study on some networks such as, Dolphin, Zachary karate club, Football club, and Facebook ego networks. We show that DOCD algorithm is capable of keeping the asymptotically same results with the existing classical centralized algorithms [1]-[5] in terms of community modularity and the number of identified communities. The DOCD algorithm can also efficiently identify the overlapped nodes and ove
The connectivity of distributed networked multi-robot systems is a crucial operational specification, since the involved robots interact/communicate locally only with their immediate neighbors. Thus, in this work, we ...
详细信息
The connectivity of distributed networked multi-robot systems is a crucial operational specification, since the involved robots interact/communicate locally only with their immediate neighbors. Thus, in this work, we propose a distributed algorithm to estimate the algebraic connectivity of the underlying communication graph, which stands as a valid connectivity metric. Our method establishes robustness and fast convergence properties that can be adjusted independently via the appropriate selection of certain design parameters. Finally, we confirm the theoretical findings through simulated paradigms and verify the superiority of our method against a well-established solution of the related literature.
distributed (decentralized) algorithms for principal component analysis of covariance matrices are well-known, and their applications in array signal processing have received more interest recently. Inspired by this, ...
详细信息
distributed (decentralized) algorithms for principal component analysis of covariance matrices are well-known, and their applications in array signal processing have received more interest recently. Inspired by this, a new distributed algorithm for the popular DOA estimation method, root-MUSIC, is proposed. The average consensus method is used to avoid the need for a fusion center in a sensor network, which makes the proposed algorithm fully distributed. In particular, the algorithm is based on a recently reported finite-time version of average consensus which converges to the exact solution in a finite number of iterations. This allows the proposed distributed root-MUSIC to achieve exactly the same performance as the centralized counterpart. The good performance of the proposed algorithm is verified by simulations.
We present a deterministic (1 + o(1))-approximation (n(1/2+o(1)) + D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model);here n is the number...
详细信息
We present a deterministic (1 + o(1))-approximation (n(1/2+o(1)) + D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model);here n is the number of nodes in the network, D is its (hop) diameter, and edge weights are positive integers from 1 to poly(n). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1 + o(1))-approximation (O) over tilde (root nD(1/4)+ D)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565-573] by a factor of as large as n1/8, and (ii) the O(is an element of(-1) log is an element of(-1))- approximation factor of Lenzen and Patt-Shamir's (O) over tilde (n(1/2+is an element of)+ D)-time algorithm [in Proceedings of STOC, 2013, pp. 381-390] within the same running time. (Throughout, we use (O) over tilde (.) to hide polylogarithmic factors in n.) Our running time matches the known time lower bound of Omega (root n/log n + D) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40-57]. It also implies a (2+ o(1))-approximation (n(1/2+o(1))+D1+o(1))time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the ``hitting set argument"" commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (no(1), o(1))-hop set of size n1+o(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths,
Differential privacy is a mathematically rigorous definition of privacy tailored to statistical analysis of large datasets. Differentially private algorithms are equipped with a parameter which controls the formal mea...
详细信息
ISBN:
(纸本)9781450385480
Differential privacy is a mathematically rigorous definition of privacy tailored to statistical analysis of large datasets. Differentially private algorithms are equipped with a parameter which controls the formal measure of privacy loss. All algorithms have utility/privacy tradeoffs, and the goal of algorithmic research in differential privacy is to optimize this *** privacy is most widely studied in the centralized model, in which a trusted and trustworthy curator has access to raw data. Deployment in industry has focused on the local model, where privacy is "rolled into" the data on the client via randomization before being collected. There is a separation between the power of the centralized and local *** a brief recap of differential privacy and its properties, we will survey a few highlights of differential privacy in a variety of distributed settings that lie between the local and centralized models, and conclude with suggestions for future research.
Wireless sensor networks (WSNs) are an important means of collecting data in a variety of situations, such as the monitoring of large or hazardous areas. The retrieval of WSN data can yield better results through the ...
详细信息
Wireless sensor networks (WSNs) are an important means of collecting data in a variety of situations, such as the monitoring of large or hazardous areas. The retrieval of WSN data can yield better results through the use of unmanned aerial vehicles (UAVs), for example, concerning the increase in the amount of data collected and the decrease in the time between the collection and use of the data. In particular, disaster areas may be left without communication resources and with high residual risk to humans, at which point a WSN can be quickly launched by air to collect relevant data until other measures can be established. The set of rules of each problem's component (e.g., number of UAVs, UAVs dislocation control, sensors, communication) is considered the approaches to solve the problem. In this meaning, some studies present approaches for the use of UAVs for the collection of WSN data, focusing primarily on optimizing the path to be covered by a single UAV and relying on long-range communication that is always available;these studies do not explore the possibility of using several UAVs or the limitations on the range of communication. This work describes DADCA, a distributed scalable approach capable of coordinating groups of UAVs in WSN data collection with restricted communication range and without the use of optimization techniques. The results reveal that the amount of data collected by DADCA is similar or superior to path optimization approaches by up to 1%. In our proposed approach, the delay in receiving sensor messages is up to 46% shorter than in other approaches, and the required processing onboard UAVs can reach less than 75% of those using optimization-based algorithms. The results indicate that the DADCA can match and even surpass other presented approaches, since the path optimization is not a focus, while also incorporating the advantages of a distributed approach.
Consensus-based distributed algorithms to estimate the number of active edges in wireless sensor networks are proposed. Conventionally, a communication link between two nodes is formed if they have sufficient transmis...
详细信息
Consensus-based distributed algorithms to estimate the number of active edges in wireless sensor networks are proposed. Conventionally, a communication link between two nodes is formed if they have sufficient transmission power to exchange information. In power constrained networks, it is crucial to know the total number of active communication links so that additional links can be created or removed depending on the power budget. We develop two distributed algorithms to estimate number of edges in the network: (a) an average consensus based algorithm which involves distributed node counting (b) a max consensus based algorithm by using the expected value of maximum of random state values. We find that average consensus based algorithm is appropriate for smaller networks, whereas, max consensus based algorithm is faster and best suited for larger networks. We derive the variance of the estimators which is proportional to square of total number of edges and inversely proportional to the number of random vectors used for estimation. The simulation results supporting the theory are also presented.
In this paper, we introduce a novel approach for rigorously verifying safety properties of state machine specifications. Our method leverages an auto-active verifier and centers around the use of action functions anno...
详细信息
In this paper, we introduce a novel approach for rigorously verifying safety properties of state machine specifications. Our method leverages an auto-active verifier and centers around the use of action functions annotated with contracts. These contracts facilitate inductive invariant checking, ensuring correctness during system execution. Our approach is further supported by the Why3-do library, which extends the Why3 tool's capabilities to verify concurrent and distributed algorithms using state machines. Two distinctive features of Why3-do are: (i) it supports specification refinement through refinement mappings, enabling hierarchical reasoning about distributed algorithms; and (ii) it can be easily extended to make verifying specific classes of systems more convenient. In particular, the library contains models allowing for message-passing algorithms to be described with programmed handlers , assuming different network semantics. A gallery of examples, all verified with Why3 using SMT solvers as proof tools, is also described in the paper. It contains several auto-actively verified concurrent and distributed algorithms, including the Paxos consensus algorithm.
Optimal transport is a framework that facilitates the most efficient allocation of a limited amount of resources. However, the most efficient allocation scheme does not necessarily preserve the most fairness. In this ...
详细信息
Optimal transport is a framework that facilitates the most efficient allocation of a limited amount of resources. However, the most efficient allocation scheme does not necessarily preserve the most fairness. In this paper, we establish a framework which explicitly considers the fairness of dynamic resource allocation over a network with heterogeneous participants. As computing the transport strategy in a centralized fashion requires significant computational resources, it is imperative to develop computationally light algorithm that can be applied to large scale problems. To this end, we develop a fully distributed algorithm for fair and dynamic optimal transport with provable convergence using alternating method of multipliers. In the designed algorithm, each corresponding pair of resource supplier and receiver compute their own solutions and update the transport schemes through negotiation iteratively which do not require a central planner. The distributed algorithm can yield a fair and efficient resource allocation mechanism over a network. We corroborate the obtained results through case studies.
We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness res...
详细信息
We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness result shows that an alpha-approximation for the minimum directed k-spanner problem for k >= 5 requires Omega(n/root alpha log n) rounds using deterministic algorithms or Omega(n/root alpha log n) rounds using randomized ones, in the Congest model of distributed computing. Combined with the constant-round O(n(epsilon))-approximation algorithm in the Local model of [L. Barenboim, M. Elkin, and C. Gavoille, Theoret. Comput. Sci., 751 (2016), pp. 2{23], as well as a polylog-round (1 + epsilon)-approximation algorithm in the Local model that we show here, our lower bounds for the CONGEST model imply a strict separation between the LOCAL and CONGEST models. Notably, to the best of our knowledge, this is the first separation between these models for a local approximation problem. Similarly, a separation between the directed and undirected cases is implied. We also prove hardness results for weighted k -spanners and for unweighted undirected k-spanners for k >= 4 in the CONGEST model. In addition, we show lower bounds for the minimum weighted 2-spanner problem in the CONGEST and LOCAL models. On the algorithmic side, apart from the aforementioned (1+ epsilon)-approximation algorithm for minimum k -spanners, our main contribution is a new distributed construction of minimum 2-spanners that uses only polynomial local computations. Our algorithm has a guaranteed approximation ratio of O(log(m/n)) for a graph with n vertices and m edges, which matches the best known ratio for polynomial-time sequential algorithms [G. Kortsarz and D. Peleg, J. algorithms, 17 (1994), pp. 222{236], and is tight if we restrict ourselves to polynomial local computations. An algorithm with this approximation factor was not previously known for the distributed setting. The number of rounds
暂无评论