BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Zvi Lotker

Zvi Lotker contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Networking and Internet ArchitectureInformation Theorymath.ITphysics.soc-phSocial and Information NetworksDistributed, Parallel, and Cluster ComputingComputational GeometryData Structures and Algorithmsmath.PRNumerical Analysis

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
10topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2015arXiv

Random Preferential Attachment Hypergraphs

The random graph model has recently been extended to a random preferential attachment graph model, in order to enable the study of general asymptotic properties in network types that are better represented by the preferential attachment evolution model than by the ordinary (uniform) evolution lodel. Analogously, this paper extends the random {\em hypergraph} model to a random {\em preferential attachment hypergraph} model. We then analyze the degree distribution of random preferential attachment hypergraphs and show that they possess heavy tail degree distribution properties similar to those of random preferential attachment graphs. However, our results show that the exponent of the degree distribution is sensitive to whether one considers the structure as a hypergraph or as a graph.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Core-Periphery in Networks: An Axiomatic Approach

Recent evidence shows that in many societies worldwide the relative sizes of the economic and social elites are continuously shrinking. Is this a natural social phenomenon? What are the forces that shape this process? We try to address these questions by studying a Core-Periphery social structure composed of a social elite, namely, a relatively small but well-connected and highly influential group of powerful individuals, and the rest of society, the periphery. Herein, we present a novel axiom-based model for the forces governing the mutual influences between the elite and the periphery. Assuming a simple set of axioms, capturing the elite's dominance, robustness, compactness and density, we are able to draw strong conclusions about the elite-periphery structure. In particular, we show that a balance of powers between elite and periphery and an elite size that is sub-linear in the network size are universal properties of elites in social networks that satisfy our axioms. We note that the latter is in controversy to the common belief that the elite size converges to a linear fraction of society (most recently claimed to be 1%). We accompany these findings with a large scale empirical study on about 100 real-world networks, which supports our results.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Generalized Perron--Frobenius Theorem for Nonsquare Matrices

The celebrated Perron--Frobenius (PF) theorem is stated for irreducible nonnegative square matrices, and provides a simple characterization of their eigenvectors and eigenvalues. The importance of this theorem stems from the fact that eigenvalue problems on such matrices arise in many fields of science and engineering, including dynamical systems theory, economics, statistics and optimization. However, many real-life scenarios give rise to nonsquare matrices. A natural question is whether the PF Theorem (along with its applications) can be generalized to a nonsquare setting. Our paper provides a generalization of the PF Theorem to nonsquare matrices. The extension can be interpreted as representing client-server systems with additional degrees of freedom, where each client may choose between multiple servers that can cooperate in serving it (while potentially interfering with other clients). This formulation is motivated by applications to power control in wireless networks, economics and others, all of which extend known examples for the use of the original PF Theorem. We show that the option of cooperation between servers does not improve the situation, in the sense that in the optimal solution no cooperation is needed, and only one server needs to serve each client. Hence, the additional power of having several potential servers per client translates into \emph{choosing} the best single server and not into \emph{sharing} the load between the servers in some way, as one might have expected. The two main contributions of the paper are (i) a generalized PF Theorem that characterizes the optimal solution for a non-convex nonsquare problem, and (ii) an algorithm for finding the optimal solution in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

SINR Diagram with Interference Cancellation

In this paper we study the reception zones of a wireless network in the SINR model with receivers that employ \emph{interference cancellation} (IC), a technique that allows a receiver to decode interfering signals, and \emph{cancel} them from the received signal in order to decode its intended message. We first derive some important topological properties of the diagram describing the reception zones and their connections to \emph{high-order Voronoi diagrams} and other related geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings (and consequently reception cells), in fact there are much fewer nonempty such cells. We prove a (tight) linear bound on the number of cells and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel measure, referred to as the \emph{Compactness Parameter}, which influences the tightness of our bounds. We then utilize the properties established for reception diagrams to devise a logarithmic time algorithm for answering \emph{point-location} queries for networks with IC.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bounds for Algebraic Gossip on Graphs

We study the stopping times of gossip algorithms for network coding. We analyze algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading Pull, Push, and Exchange. The stopping time of algebraic gossip is known to be linear for the complete graph, but the question of determining a tight upper bound or lower bounds for general graphs is still open. We take a major step in solving this question, and prove that algebraic gossip on any graph of size n is O(D*n) where D is the maximum degree of the graph. This leads to a tight bound of Theta(n) for bounded degree graphs and an upper bound of O(n^2) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of Omega(n^2). Our proofs use a novel method that relies on Jackson's queuing theorem to analyze the stopping time of network coding; this technique is likely to become useful for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Data Interpolation: An Efficient Sampling Alternative for Big Data Aggregation

Given a large set of measurement sensor data, in order to identify a simple function that captures the essence of the data gathered by the sensors, we suggest representing the data by (spatial) functions, in particular by polynomials. Given a (sampled) set of values, we interpolate the datapoints to define a polynomial that would represent the data. The interpolation is challenging, since in practice the data can be noisy and even Byzantine, where the Byzantine data represents an adversarial value that is not limited to being close to the correct measured data. We present two solutions, one that extends the Welch-Berlekamp technique in the case of multidimensional data, and copes with discrete noise and Byzantine data, and the other based on Arora and Khot techniques, extending them in the case of multidimensional noisy and Byzantine data.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

From Caesar to Twitter: An Axiomatic Approach to Elites of Social Networks

In many societies there is an elite, a relatively small group of powerful individuals that is well-connected and highly influential. Since the ancient days of Julius Caesar's senate of Rome to the recent days of celebrities on Twitter, the size of the elite is a result of conflicting social forces competing to increase or decrease it. The main contribution of this paper is the answer to the question how large the elite is at equilibrium. We take an axiomatic approach to solve this: assuming that an elite exists and it is influential, stable and either minimal or dense, we prove that its size must be $Θ(\sqrt{m})$ (where $m$ is the number of edges in the network). As an approximation for the elite, we then present an empirical study on nine large real-world networks of the subgraph formed by the highest degree nodes, also known as the rich-club. Our findings indicate that elite properties such as disproportionate influence, stability and density of $Θ(\sqrt{m})$-rich-clubs are universal properties and should join a growing list of common phenomena shared by social networks and complex systems such as "small world," power law degree distributions, high clustering, etc.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Self-Adjusting Networks to Minimize Expected Path Length

Given a network infrastructure (e.g., data-center or on-chip-network) and a distribution on the source-destination requests, the expected path (route) length is an important measure for the performance, efficiency and power consumption of the network. In this work we initiate a study on self-adjusting networks: networks that use local-distributed mechanisms to adjust the position of the nodes (e.g., virtual machines) in the network to best fit the route requests distribution. Finding the optimal placement of nodes is defined as the minimum expected path length (MEPL) problem. This is a generalization of the minimum linear arrangement (MLA) problem where the network infrastructure is a line and the computation is done centrally. In contrast to previous work, we study the distributed version and give efficient and simple approximation algorithms for interesting and practically relevant special cases of the problem. In particular, we consider grid networks in which the distribution of requests is a symmetric product distribution. In this setting, we show that a simple greedy policy of position switching between neighboring nodes to locally minimize an objective function, achieves good approximation ratios. We are able to prove this result using the useful notions of expected rank of the distribution and the expected distance to the center of the graph.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Efficient Joint Network-Source Coding for Multiple Terminals with Side Information

Consider the problem of source coding in networks with multiple receiving terminals, each having access to some kind of side information. In this case, standard coding techniques are either prohibitively complex to decode, or require network-source coding separation, resulting in sub-optimal transmission rates. To alleviate this problem, we offer a joint network-source coding scheme based on matrix sparsification at the code design phase, which allows the terminals to use an efficient decoding procedure (syndrome decoding using LDPC), despite the network coding throughout the network. Via a novel relation between matrix sparsification and rate-distortion theory, we give lower and upper bounds on the best achievable sparsification performance. These bounds allow us to analyze our scheme, and, in particular, show that in the limit where all receivers have comparable side information (in terms of conditional entropy), or, equivalently, have weak side information, a vanishing density can be achieved. As a result, efficient decoding is possible at all terminals simultaneously. Simulation results motivate the use of this scheme at non-limiting rates as well.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Order Optimal Information Spreading Using Algebraic Gossip

In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate $k$ distinct messages to all $n$ nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of $O((k+\log n + D)Δ)$ rounds with high probability, where $D$ and $Δ$ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of $k$ this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is \emph{order optimal} and the stopping time is $Θ(k + D)$. To eliminate the factor of $Δ$ from the upper bound we propose a non-uniform gossip protocol, TAG, which is based on algebraic gossip and an arbitrary spanning tree protocol $§$. The stopping time of TAG is $O(k+\log n +d(§)+t(§))$, where $t(§)$ is the stopping time of the spanning tree protocol, and $d(§)$ is the diameter of the spanning tree. We provide two general cases in which this bound leads to an order optimal protocol. The first is for $k=Ω(n)$, where, using a simple gossip broadcast protocol that creates a spanning tree in at most linear time, we show that TAG finishes after $Θ(n)$ rounds for any graph. The second uses a sophisticated, recent gossip protocol to build a fast spanning tree on graphs with large weak conductance. In turn, this leads to the optimally of TAG on these graphs for $k=Ω(\mathrm{polylog}(n))$. The technique used in our proofs relies on queuing theory, which is an interesting approach that can be useful in future gossip analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Topology of Wireless Communication

In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a \emph{reception map}. In the SINR model, the resulting \emph{SINR diagram} partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. We consider the general case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques as well as the theoretical challenge of understanding the geometry of SINR diagrams. We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line. In addition, one of our key results concerns the behavior of a $(d+1)$-dimensional map. Specifically, although the $d$-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected. In addition, as a step toward establishing a weaker form of convexity for the $d$-dimensional map, we study the interference function and show that it satisfies the maximum principle. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.

0 citations0 reviewsNo code linkedOpen access