In many social networks, there exist two types of users that exhibit different influence and different behavior. For instance, statistics have shown that less than 1% of the Twitter users (e.g. entertainers, politicians, writers) produce 50% of its content, while the others (e.g. fans, followers, readers) have much less influence and completely different social behavior. In this paper, we define and explore a novel problem called community kernel detection in order to uncover the hidden community structure in large social networks. We discover that influential users pay closer attention to those who are more similar to them, which leads to a natural partition into different community kernels. We propose Greedy and We BA, two efficient algorithms for finding community kernels in large social networks. Greedy is based on maximum cardinality search, while We BA formalizes the problem in an optimization framework. We conduct experiments on three large social networks: Twitter, Wikipedia, and Coauthor, which show that We BA achieves an average 15%-50% performance improvement over the other state-of-the-art algorithms, and We BA is on average 6-2,000 times faster in detecting community kernels.

Extensive research has demonstrated the potential improvement in physical layer performance when multiple radios transmit concurrently in the same radio channel. We consider how such cooperation affects the requirements for full connectivity and percolation in large wireless ad hoc networks. Both noncoherent and coherent cooperative transmission are considered. For one-dimensional (1-D) extended networks, in contrast to noncooperative networks, for any path loss exponent less than or equal to one, full connectivity occurs under the noncoherent cooperation model with probability one for any node density. Conversely, there is no full connectivity with probability one when the path loss exponent exceeds one, and the network does not percolate for any node density if the path loss exponent exceeds two. In two-dimensional (2-D) extended networks with noncoherent cooperation, for any path loss exponent less than or equal to two, full connectivity is achieved for any node density. Conversely, there is no full connectivity when the path loss exponent exceeds two, but the cooperative network percolates for node densities above a threshold which is strictly less than that of the noncooperative network. A less conclusive set of results is presented for the coherent case. Hence, even relatively simple noncoherent cooperation improves the connectivity of large ad hoc networks.

Connectivity and capacity are two measures for the performance of mobile ad hoc networks that have been studied extensively under standard point-to-point physical layer assumptions. However, extensive recent research at the physical layer has demonstrated the improvement in performance possible when multiple radios concurrently transmit in the same radio channel. In this paper, we consider how such physical layer cooperation improves the connectivity in wireless ad hoc networks. In particular, with noncoherent cooperation at the physical layer, we consider conditions on the node density λ (or, equivalently, the transmit power) for full connectivity and percolation for large networks in various dimensions and with various path loss exponents α. For one-dimensional (1-D) extended networks, in sharp contrast to noncooperative networks, we demonstrate that full connectivity can be realized under certain conditions. In particular, for any node density with path loss exponent α < 1, or for node density λ > 2 when α = 1, full connectivity occurs with probability one. Conversely, we demonstrate that, under noncoherent cooperation, there is no full connectivity with probability one when α < 1. In two-dimensional (2-D) extended networks with noncoherent cooperation, for any node density with α < 2, or for node density λ Ū 5 when α = 2, full connectivity is achieved. Conversely, there is no full connectivity with probability one when α > 2, but we prove that, for α ≥ 4, the percolation threshold of the noncoherent cooperative network is strictly less than that of the noncooperative network. Analogous results are presented for dense networks. Hence, the main conclusion is that even relatively simple physical layer cooperation in the form of noncoherent power summing can substantially improve the connectivity of large ad hoc networks.