Recent developments on identifying the community structures in real-world networks have established that the community structure may be either disjoint community set (DCS) or overlapping community set (OCS), showing high resemblance with each other. Still, given a network, researchers mostly followed distinct approaches to achieve optimal solutions, either for DCS or for OCS. Moreover, prior knowledge of community structure is needed to select the appropriate class of algorithms, since one cannot produce the optimal solution for the other. In this article, a comprehensive two-phase approach based on genetic algorithm (GA) is proposed that can be applied to any small-world network to generate the DCS and the OCS very fast without any prior knowledge of the community structure. In the first phase, an upper bound on the mean path length of a community is applied, relative to the equivalent Erdős–Rényi (E–R) random graph that expedites the convergence significantly. In the second phase, the search space is reduced considerably, by selecting a smaller subset of boundary nodes of the DCS generated in the first phase, to be manipulated probabilistically. To the best of our knowledge, we are the first to consider the mean path length of the community as a key parameter for finding the good quality communities at the earliest. Experimental study on six synthetic networks and five real-world networks shows that the proposed approach not only outperforms the state-of-the-art algorithms in terms of quality and scalability, but its parallel implementation also improves the speedup significantly.

This paper focuses on the data aggregation problem to two aggregators in a data center network under the constraint that each source rack must use a single path to each aggregator. We derive bounds on the approximation ratios of two classes of aggregation algorithms- Restricted 1-Round (R1R) and Restricted 2-Round (R2R). We achieve tighter bounds for the problem with additional constraints on the inputs. We propose another strategy using the 2Chain topology for k = 2, where k denotes the maximum degree of each top-of-rack(ToR) switch (number of uplinks in a ToR switch) in the data center and show that the optimal 2Chain cannot have an aggregation time greater than that of the optimal R1R and R2R topologies. For k ≥ 4, we propose a 1-round aggregation algorithm (1R) that uses trees for aggregation. Experimental results illustrate that 1R, R2R and R1R reduce the aggregation time by up to 85, 67 and 67 percent respectively for k = 4 relative to the two-round aggregation algorithm proposed by Wang et al. Moreover, for k = 2, the 2Chain can reduce the aggregation time up to 42 and 24 percent respectively relative to R1R and R2R.

In this paper we focus on the problem of data aggregation using two aggregators in a data center network, where the source racks are allowed to split their data and send to the aggregators using multiple paths. We show that the problem of finding a topology that minimizes aggregation time is NP-hard fork = 2, 3, 4, where k is the maximum degree of each ToR switch (number of uplinks in a top-of-rack switch) in the data center. We also show that the problem becomes solvable in polynomial time fork = 5 and 6 and conjecture the same for k > 6. Experimental results show that, for k = 6, our topology optimization algorithm reduces the aggregation time by as much as 83.32 percent and reduces total network traffic by as much as 99.5 percent relative to the torus heuristic, proposed in [1], which readily proves the significant improvement in performance achieved by the proposed algorithm.

Data aggregation is a critical operation in many big-data applications; for example, data residing in several source racks (mappers) are to be aggregated into one or more specified racks called aggregators (reducers) in the data center network during the shuffle phase of a map-reduce task. In this paper, we explore algorithms for data aggregation to two aggregators in a data center network under the constraint that data from a source rack must be routed to each aggregator using a single path. We derive bounds on the approximation ratios of two classes of aggregation algorithms- Restricted 1-Round (R1R) and Restricted 2-Round (R2R). For the case when racks have exactly 2 optical links (uplinks in Top-of-Rack switches), we propose another strategy using the 2Chain topology for aggregation and show that the optimal 2Chain cannot have an aggregation time greater than that of the optimal R1R and R2R topologies. For the case when racks have at least 4 optical links, we propose a 1-round aggregation algorithm (1R) that uses tree topology for aggregation. Experimental results indicate that, when racks have 4 optical links, 1R, R2R and R1R reduce the aggregation time by up to 85%, 67% and 67% respectively, relative to the two-round aggregation algorithm proposed by Wang et al. Moreover, the 2Chain can reduce the aggregation time up to 42% and 24% respectively relative to R1R and R2R, when racks have exactly 2 optical links.

In the above paper[1], one author was inadvertently left out of the byline of the paper. The byline should have read as follows:

We consider the problem of data aggregation using two aggregators. We assume that the source racks can split the data they need to send to the aggregators across multiple paths. We show that obtaining a topology that minimizes aggregation time is NP-hard for k = 2, 3,4, where k the degree of ToR (top-of-rack) switches. We also show that an optimal topology can be computed in polynomial time for k = 5 and 6 and conjecture this to be the case when k > 6 as well. Experimental results show that, when k = 6, our topology optimization algorithm reduces the aggregation time by as much as 83.3% and reduces total network traffic by as much as 99.5% relative to the torus heuristic, proposed by [1].

In this paper, we show that the problem of configuring the topology of a data center network to optimize data aggregation is NP-hard even when the number of aggregators is 1. Further, the approximation ratio of the algorithm proposed by Wang, Ng, and Shaikh [3] for the case of a single aggregator is (k+1)/2, where k is the degree of ToR (top-of-rack) switches and this algorithm also exhibits an anomalous behavior-increase in the switch degree may result in an increase in the aggregation time. By comparison, if topology configuration is done using the longest processing time (LPT) scheduling rule, the approximation ratio is (4/3-1/(3k)). We show that for every instance of the single aggregator topology configuration problem, the time required to aggregate using the LPT configuration is no more than that using the Wang et al. rule. By coupling the LPT rule with the rule of Wang et al., we achieve a better throughput as promised by LPT and at the same time reduce the total network traffic. Experimental results show that the LPT rule reduces aggregation time by up to 90% compared to the Wang et al. rule. The reduction in aggregation time afforded by a known improvement, COMBINE, of LPT relative to Wang et al. is up to 90.5%. More interestingly, when either of the LPT rule or COMBINE is augmented with the Wang et al. rule, total network traffic is reduced by up to 90% relative to using LPT and COMBINE with chains.

We study the influence maximization problem (IMP) in multiple online social networks (OSNs). In contrast to most of the previous works on influence maximization which only focused on a single network, our work is the first one to evaluate the propagation of influence across multiple networks simultaneously. In this paper, we first propose a general representation for multiple networks using universal ids for the users. We next introduce a powerful coupling scheme which reduces the multiple networks into a single network without changing influencing properties, thereby allowing us to solve the problem in the reduced network. Moreover, the coupling scheme is also an efficient tool to investigate various aspects of the influence propagation on multiple OSNs. The extensive experiments on real-world and synthesized datasets not only confirm the quality of the solution but also reveal interesting insights into the behavior of influence propagation in and across the networks.

The least cost influence (LCI) problem, which asks to identify a minimum number of seed users who can eventually influence a large number of users, has become one of the central research topics recently in online social networks (OSNs). However, existing works mostly focused on a single network while users nowadays often join several OSNs. Thus, it is crucial to investigate the influence in multiplex networks, i.e. the influence is diffused across a set of networks via shared users, in order to obtain the best set of seed users.In this paper, we propose a unified framework to represent and analyze the influence diffusion in multiplex networks. More specifically, we tackle the LCI problem in multiplex OSNs by reducing multiplex networks to a single network via various coupling schemes while preserving the most influence propagation properties. Besides the coupling schemes to represent the diffusion process, the framework also includes the influence relay, a new metric to measure the flow of influence inside and between networks. The experiments on both real and synthesized datasets validate the effectiveness of the coupling schemes as well as provide some interesting insights into the process of influence propagation in multiplex networks.