Forming Networks of Strategic Agents with Desired Topologies

Many networks such as social networks and organizational networks in global companies consist of self-interested agents. The topology of these networks often plays a crucial role in important tasks such as information diffusion and information extraction. Consequently, growing a stable network having a certain topology is of interest. Motivated by this, we study the following important problem: given a certain desired network topology, under what conditions would best response (link addition/deletion) strategies played by self-interested agents lead to formation of a stable network having that topology. We study this interesting reverse engineering problem by proposing a natural model of recursive network formation and a utility model that captures many key features. Based on this model, we analyze relevant network topologies and derive a set of sufficient conditions under which these topologies emerge as pairwise stable networks, wherein no node wants to delete any of its links and no two nodes would want to create a link between them.

Scalable Preference Aggregation in Social Networks

In social choice theory, preference aggregation refers to computing an aggregate preference over a set of alternatives given individual preferences of all the agents. In real-world scenarios, it may not be feasible to gather preferences from all the agents. Moreover, determining the aggregate preference is computationally intensive. In this paper, we show that the aggregate preference of the agents in a social network can be computed efficiently and with sufficient accuracy using preferences elicited from a small subset of critical nodes in the network. Our methodology uses a model developed based on real-world data obtained using a survey on human subjects, and exploits network structure and homophily of relationships. Our approach guarantees good performance for aggregation rules that satisfy a property which we call expected weak insensitivity. We demonstrate empirically that many practically relevant aggregation rules satisfy this property. We also show that two natural objective functions in this context satisfy certain properties, which makes our methodology attractive for scalable preference aggregation over large scale social networks. We conclude that our approach is superior to random polling while aggregating preferences related to individualistic metrics, whereas random polling is acceptable in the case of social metrics.

Frustration induced oscillator death on networks

An array of identical maps with Ising symmetry, with both positive and negative couplings, is studied. We divide the maps into two groups, with positive intra-group couplings and negative inter-group couplings. This leads to antisynchronization between the two groups which have the same stability properties as the synchronized state. Introducing a certain degree of randomness in signs of these couplings destabilizes the anti-synchronized state. Further increasing the randomness in signs of these couplings leads to oscillator death. This is essentially a frustration induced phenomenon. We explain the observed results using the theory of random matrices with nonzero mean. We briefly discuss applications to coupled differential equations. (C) 2013 AIP Publishing LLC.

Optimal incentive timing strategies for product marketing on social networks

We consider the problem of devising incentive strategies for viral marketing of a product. In particular, we assume that the seller can influence penetration of the product by offering two incentive programs: a) direct incentives to potential buyers (influence) and b) referral rewards for customers who influence potential buyers to make the purchase (exploit connections). The problem is to determine the optimal timing of these programs over a finite time horizon. In contrast to algorithmic perspective popular in the literature, we take a mean-field approach and formulate the problem as a continuous-time deterministic optimal control problem. We show that the optimal strategy for the seller has a simple structure and can take both forms, namely, influence-and-exploit and exploit-and-influence. We also show that in some cases it may optimal for the seller to deploy incentive programs mostly for low degree nodes. We support our theoretical results through numerical studies and provide practical insights by analyzing various scenarios.

Threats and trade-fffs in resource critical crowdsourcing tasks over networks

In recent times, crowdsourcing over social networks has emerged as an active tool for complex task execution. In this paper, we address the problem faced by a planner to incen-tivize agents in the network to execute a task and also help in recruiting other agents for this purpose. We study this mecha-nism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner’s goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We define a set of fairness properties that should beideally satisfied by a crowdsourcing mechanism. We prove that no mechanism can satisfy all these properties simultane-ously. We relax some of these properties and define their ap-proximate counterparts. Under appropriate approximate fair-ness criteria, we obtain a non-trivial family of payment mech-anisms. Moreover, we provide precise characterizations of cost critical and time critical mechanisms.

Packet flow analysis in IP networks using data-flow analysis

Static analysis (aka offline analysis) of a model of an IP network is useful for understanding, debugging, and verifying packet flow properties of the network. Data-flow analysis is a method that has typically been applied to static analysis of programs. We propose a new, data-flow based approach for static analysis of packet flows in networks. We also investigate an application of our analysis to the problem of inferring a high-level policy from the network, which has been addressed in the past only for a single router.

Joint Routing, Scheduling and Power Control in Multihop MIMO Networks with MAC and Broadcast Links

We consider the problem of joint routing, scheduling and power control in a multihop wireless network when the nodes have multiple antennas. We focus on exploiting the multiple degrees-of-freedom available at each transmitter and receiver due to multiple antennas. Specifically we use multiple antennas at each node to form multiple access and broadcast links in the network rather than just point to point links. We show that such a generic transmission model improves the system performance significantly. Since the complexity of the resulting optimization problem is very high, we also develop efficient suboptimal solutions for joint routing, scheduling and power control in this setup.

On the feasibility of network alignment for three-source three-destination Multiple Unicast networks with delays

A transform approach to network coding was in-troduced by Bavirisetti et al. (arXiv:1103.3882v3 [cs.IT]) as a tool to view wireline networks with delays as k-instantaneous networks (for some large k). When the local encoding kernels (LEKs) of the network are varied with every time block of length k >1, the network is said to use block time varying LEKs. In this work, we propose a Precoding Based Network Alignment (PBNA) scheme based on transform approach and block time varying LEKs for three-source three-destination multiple unicast network with delays (3-S3-D MUN-D). In a recent work, Menget al. (arXiv:1202.3405v1 [cs.IT]) reduced the infinite set of sufficient conditions for feasibility of PBNA in a three-source three-destination instantaneous multiple unicast network as given by Das et al. (arXiv:1008.0235v1 [cs.IT]) to a finite set and also showed that the conditions are necessary. We show that the conditions of Meng et al. are also necessary and sufficient conditions for feasibility of PBNA based on transform approach and block time varying LEKs for 3-S3-D MUN-D.

Better QOS with W/T SPR codes for the transmission of multimedia signals in Optical CDMA networks

In this paper optical code-division multiple-access (O-CDMA) packet network is considered, which offers inherent security in the access networks. The application of O-CDMA to multimedia transmission (voice, data, and video) is investigated. The simultaneous transmission of various services is achieved by assigning to each user unique multiple code signatures. Thus, by applying a parallel mapping technique, we achieve multi-rate services. A random access protocol is proposed, here, where all distinct codes are used, for packet transmission. The codes, Optical Orthogonal Code (OOC), or 1D codes and Wavelength/Time Single-Pulse-per-Row (W/T SPR), or 2D codes, are analyzed. These 1D and 2D codes with varied weight are used to differentiate the Quality of Service (QoS). The theoretical bit error probability corresponding to the quality of each service is established using 1D and 2D codes in the receiver noiseless case and compared. The results show that, using 2D codes QoS in multimedia transmission is better than using 1D codes.

A transform approach to linear network coding for acyclic networks with delay

The algebraic formulation for linear network coding in acyclic networks with each link having an integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes at any given time instant is a Fq-linear combination of the input symbols across different generations, where Fq denotes the field over which the network operates. We use finite-field discrete Fourier transform (DFT) to convert the output symbols at the sink nodes at any given time instant into a Fq-linear combination of the input symbols generated during the same generation. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (non-transform) approach if and only if there exists a network code satisfying sink demands in the transform approach. Furthermore, assuming time invariant local encoding kernels, we show that the transform method can be employed to achieve half the rate corresponding to the individual source-destination mincut (which are assumed to be equal to 1) for some classes of three-source three-destination multiple unicast network with delays using alignment strategies when the zero-interference condition is not satisfied.

A Multicast Authentication Protocol (MAP) for Dynamic Multicast Groups in Wireless Networks

In this paper, we have proposed a centralized multicast authentication protocol (MAP) for dynamic multicast groups in wireless networks. In our protocol, a multicast group is defined only at the time of the multicasting. The authentication server (AS) in the network generates a session key and authenticates it to each of the members of a multicast group using the computationally inexpensive least common multiple (LCM) method. In addition, a pseudo random function (PRF) is used to bind the secret keys of the network members with their identities. By doing this, the AS is relieved from storing per member secrets in its memory, making the scheme completely storage scalable. The protocol minimizes the load on the network members by shifting the computational tasks towards the AS node as far as possible. The protocol possesses a membership revocation mechanism and is protected against replay attack and brute force attack. Analytical and simulation results confirm the effectiveness of the proposed protocol.

Comparison of OpAmp based and comparator based switched capacitor filter

Comparator based switched capacitor circuits provide an excellent opportunity to design sampled data systems where the virtual ground condition is detected rather than being continuously forced with negative feedback in Opamp based circuits. This work is an application of this concept to design a 1 st order 330 KHz cutoff frequency Lowpass filter operating at 10 MHz sampling frequency in 0.13μm technology and 1.2 V supply voltage. The Comparator Based Switched Capacitor (CBSC) filter is compared with conventional Two stage Miller compensated Operational amplifier based switched capacitor filter. It is shown that CBSC filter relaxes the constraints like speed ,linearity, gain, stability which would otherwise be hard to satisfy in scaled technologies in Opamp based circuits. The designed CBSC based lowpass filter provides significant power savings compared to traditional Opamp based switched capacitor filter.

On interference alignment for symmetrically connected interference networks with line of sight channels at finite powers

In this work, interference alignment for a class of Gaussian interference networks with general message demands, having line of sight (LOS) channels, at finite powers is considered. We assume that each transmitter has one independent message to be transmitted and the propagation delays are uniformly distributed between 0 and (L - 1) (L >; 0). If receiver-j, j ∈{1,2,..., J}, requires the message of transmitter-i, i ∈ {1, 2, ..., K}, we say (i, j) belongs to a connection. A class of interference networks called the symmetrically connected interference network is defined as a network where, the number of connections required at each transmitter-i is equal to ct for all i and the number of connections required at each receiver-j is equal to cr for all j, for some fixed positive integers ct and cr. For such networks with a LOS channel between every transmitter and every receiver, we show that an expected sum-spectral efficiency (in bits/sec/Hz) of at least K/(e+c1-1)(ct+1) (ct/ct+1)ct log2 (1+min(i, j)∈c|hi, j|2 P/WN0) can be achieved as the number of transmitters and receivers tend to infinity, i.e., K, J →∞ where, C denotes the set of all connections, hij is the channel gain between transmitter-i and receiver-j, P is the average power constraint at each transmitter, W is the bandwidth and N0 W is the variance of Gaussian noise at each receiver. This means that, for an LOS symmetrically connected interference network, at any finite power, the total spectral efficiency can grow linearly with K as K, J →∞. This is achieved by extending the time domain interference alignment scheme proposed by Grokop et al. for the k-user Gaussian interference channel to interference networks.

Game theoretic analysis of collusions in nonneutral networks

This paper studies the impact of exclusive contracts between a content provider (CP) and an internet service provider (ISP) in a nonneutral network. We consider a simple linear demand function for the CPs. We studywhen an exclusive contract is benefcial to the colluding pair and evaluate its impact on the noncolluding players at equilibrium. For the case of two CPs and one ISP we show that collusion may not always be benefcial. We derive an explicit condition in terms of the advertisement revenues of the CPs that tells when a collusion is proftable to the colluding entities.

Joint Scheduling & Jamming for Data Secrecy in Wireless Networks

The broadcast nature of the wireless medium jeopardizes secure transmissions. Cryptographic measures fail to ensure security when eavesdroppers have superior computational capability; however, it can be assured from information theoretic security approaches. We use physical layer security to guarantee non-zero secrecy rate in single source, single destination multi-hop networks with eavesdroppers for two cases: when eavesdropper locations and channel gains are known and when their positions are unknown. We propose a two-phase solution which consists of finding activation sets and then obtaining transmit powers subject to SINR constraints for the case when eavesdropper locations are known. We introduce methods to find activation sets and compare their performance. Necessary but reasonable approximations are made in power minimization formulations for tractability reasons. For scenarios with no eavesdropper location information, we suggest vulnerability region (the area having zero secrecy rate) minimization over the network. Our results show that in the absence of location information average number of eavesdroppers who have access to data is reduced.