Source author record

Saswata Shannigrahi

Saswata Shannigrahi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO physics.soc-ph Social and Information Networks Data Structures and Algorithms

Catalog footprint

What is connected

5works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

preprint2022arXiv

On the Rise and Fall of Online Social Networks

The rise and fall of online social networks recently generated an enormous amount of interest among people, both inside and outside of academia. Gillette [Businessweek magazine, 2011] did a detailed analysis of MySpace, which started losing its popularity since 2008. Cannarella and Spechler [ArXiv, 2014] used a model of disease spread to explain the rise and fall of MySpace. In this paper, we present a graph theoretical model that may be able to provide an alternative explanation for the rise and fall of online social networks. Our model is motivated by the well-known Barabasi-Albert model of generating random scale-free networks using preferential attachment or `rich-gets-richer' phenomenon. As shown by our empirical analysis, we conjecture that such an online social network growth model is inherently flawed as it fails to maintain the stability of such networks while ensuring their growth. In the process, we also conjecture that our model of preferential attachment also exhibits scale-free phenomenon.

preprint2016arXiv

A new hierarchical clustering algorithm to identify non-overlapping like-minded communities

A network has a non-overlapping community structure if the nodes of the network can be partitioned into disjoint sets such that each node in a set is densely connected to other nodes inside the set and sparsely connected to the nodes out- side it. There are many metrics to validate the efficacy of such a structure, such as clustering coefficient, betweenness, centrality, modularity and like-mindedness. Many methods have been proposed to optimize some of these metrics, but none of these works well on the recently introduced metric like-mindedness. To solve this problem, we propose a be- havioral property based algorithm to identify communities that optimize the like-mindedness metric and compare its performance on this metric with other behavioral data based methodologies as well as community detection methods that rely only on structural data. We execute these algorithms on real-life datasets of Filmtipset and Twitter and show that our algorithm performs better than the existing algorithms with respect to the like-mindedness metric.

preprint2014arXiv

A Lower Bound on the Crossing Number of Uniform Hypergraphs

In this paper, we consider the embedding of a complete $d$-uniform geometric hypergraph with $n$ vertices in general position in $\mathbb{R}^d$, where each hyperedge is represented as a $(d-1)$-simplex, and a pair of hyperedges is defined to cross if they are vertex-disjoint and contains a common point in the relative interior of the simplices corresponding to them. As a corollary of the Van Kampen-Flores Theorem, it can be seen that such a hypergraph contains $Ω(\frac{2^d}{\sqrt{d}})$ $n\choose 2d$ crossing pairs of hyperedges. Using Gale Transform and Ham Sandwich Theorem, we improve this lower bound to $Ω(\frac{2^d \log d}{\sqrt{d}})$ $n\choose 2d$.

preprint2014arXiv

On the construction of non-2-colorable uniform hypergraphs

The problem of 2-coloring uniform hypergraphs has been extensively studied over the last few decades. An n-uniform hypergraph is not 2-colorable if its vertices can't be colored with two colors, Red and Blue, such that every hyperedge contains Red as well as Blue vertices. The least possible number of hyperedges in an n-uniform hypergraph which is not 2-colorable is denoted by m(n). In this paper, we consider the problem of finding an upper bound on m(n) for small values of n. We provide constructions which improve the existing results for some such values of n. We obtain the first improvement in the case of n=8.

preprint2013arXiv

New Online Algorithm for Dynamic Speed Scaling with Sleep State

In this paper, we consider an energy-efficient scheduling problem where $n$ jobs $J_1, J_2, ..., J_n$ need to be executed such that the total energy usage of these jobs is minimized while ensuring that each job is finished within it's deadline. We work in an online setting where a job is known only at it's arrival time, along with it's processing volume and deadline. In such a setting, the currently best-known algorithm by Han et al. \cite{han} provides a competitive ratio max $\{4, 2 + α^α\}$ of energy usage. In this paper, we present a new online algorithm SqOA which provides a competitive ratio max $\{4, 2 + (2-1/α)^α2^{α-1}\}$ of energy usage. For $α\geq 3$, the competitive ratio of our algorithm is better than that of any other existing algorithms for this problem.