Matching Items (6)
Description
US Senate is the venue of political debates where the federal bills are formed and voted. Senators show their support/opposition along the bills with their votes. This information makes it possible to extract the polarity of the senators. Similarly, blogosphere plays an increasingly important role as a forum for public debate. Authors display sentiment toward issues, organizations or people using a natural language.
In this research, given a mixed set of senators/blogs debating on a set of political issues from opposing camps, I use signed bipartite graphs for modeling debates, and I propose an algorithm for partitioning both the opinion holders (senators or blogs) and the issues (bills or topics) comprising the debate into binary opposing camps. Simultaneously, my algorithm scales the entities on a univariate scale. Using this scale, a researcher can identify moderate and extreme senators/blogs within each camp, and polarizing versus unifying issues. Through performance evaluations I show that my proposed algorithm provides an effective solution to the problem, and performs much better than existing baseline algorithms adapted to solve this new problem. In my experiments, I used both real data from political blogosphere and US Congress records, as well as synthetic data which were obtained by varying polarization and degree distribution of the vertices of the graph to show the robustness of my algorithm.
I also applied my algorithm on all the terms of the US Senate to the date for longitudinal analysis and developed a web based interactive user interface www.PartisanScale.com to visualize the analysis.
US politics is most often polarized with respect to the left/right alignment of the entities. However, certain issues do not reflect the polarization due to political parties, but observe a split correlating to the demographics of the senators, or simply receive consensus. I propose a hierarchical clustering algorithm that identifies groups of bills that share the same polarization characteristics. I developed a web based interactive user interface www.ControversyAnalysis.com to visualize the clusters while providing a synopsis through distribution charts, word clouds, and heat maps.
In this research, given a mixed set of senators/blogs debating on a set of political issues from opposing camps, I use signed bipartite graphs for modeling debates, and I propose an algorithm for partitioning both the opinion holders (senators or blogs) and the issues (bills or topics) comprising the debate into binary opposing camps. Simultaneously, my algorithm scales the entities on a univariate scale. Using this scale, a researcher can identify moderate and extreme senators/blogs within each camp, and polarizing versus unifying issues. Through performance evaluations I show that my proposed algorithm provides an effective solution to the problem, and performs much better than existing baseline algorithms adapted to solve this new problem. In my experiments, I used both real data from political blogosphere and US Congress records, as well as synthetic data which were obtained by varying polarization and degree distribution of the vertices of the graph to show the robustness of my algorithm.
I also applied my algorithm on all the terms of the US Senate to the date for longitudinal analysis and developed a web based interactive user interface www.PartisanScale.com to visualize the analysis.
US politics is most often polarized with respect to the left/right alignment of the entities. However, certain issues do not reflect the polarization due to political parties, but observe a split correlating to the demographics of the senators, or simply receive consensus. I propose a hierarchical clustering algorithm that identifies groups of bills that share the same polarization characteristics. I developed a web based interactive user interface www.ControversyAnalysis.com to visualize the clusters while providing a synopsis through distribution charts, word clouds, and heat maps.
ContributorsGokalp, Sedat (Author) / Davulcu, Hasan (Thesis advisor) / Sen, Arunabha (Committee member) / Liu, Huan (Committee member) / Woodward, Mark (Committee member) / Arizona State University (Publisher)
Created2015
Description
On Android, existing security procedures require apps to request permissions for access to sensitive resources.
Only when the user approves the requested permissions will the app be installed.
However, permissions are an incomplete security mechanism.
In addition to a user's limited understanding of permissions, the mechanism does not account for the possibility that different permissions used together have the ability to be more dangerous than any single permission alone.
Even if users did understand the nature of an app's requested permissions, this mechanism is still not enough to guarantee that a user's information is protected.
Applications can potentially send or receive sensitive information from other applications without the required permissions by using intents.
In other words, applications can potentially collaborate in ways unforeseen by the user, even if the user understands the permissions of each app independently.
In this thesis, we present several graph-based approaches to address these issues.
We determine the permissions of an app and generate scores based on our assigned value of certain resources.
We analyze these scores overall, as well as in the context of the app's category as determined by Google Play.
We show that these scores can be used to identify overzealous apps, as well as apps that do not properly fit within their category.
We analyze potential interactions between different applications using intents, and identify several promiscuous apps with low permission scores, showing that permissions alone are not sufficient to evaluate the security risks of an app.
Our analyses can form the basis of a system to assist users in identifying apps that can potentially compromise user privacy.
Only when the user approves the requested permissions will the app be installed.
However, permissions are an incomplete security mechanism.
In addition to a user's limited understanding of permissions, the mechanism does not account for the possibility that different permissions used together have the ability to be more dangerous than any single permission alone.
Even if users did understand the nature of an app's requested permissions, this mechanism is still not enough to guarantee that a user's information is protected.
Applications can potentially send or receive sensitive information from other applications without the required permissions by using intents.
In other words, applications can potentially collaborate in ways unforeseen by the user, even if the user understands the permissions of each app independently.
In this thesis, we present several graph-based approaches to address these issues.
We determine the permissions of an app and generate scores based on our assigned value of certain resources.
We analyze these scores overall, as well as in the context of the app's category as determined by Google Play.
We show that these scores can be used to identify overzealous apps, as well as apps that do not properly fit within their category.
We analyze potential interactions between different applications using intents, and identify several promiscuous apps with low permission scores, showing that permissions alone are not sufficient to evaluate the security risks of an app.
Our analyses can form the basis of a system to assist users in identifying apps that can potentially compromise user privacy.
ContributorsGibson, Aaron (Author) / Bazzi, Rida (Thesis advisor) / Ahn, Gail-Joon (Committee member) / Walker, Erin (Committee member) / Arizona State University (Publisher)
Created2015
Description
Social media has become popular in the past decade. Facebook for example has 1.59 billion active users monthly. With such massive social networks generating lot of data, everyone is constantly looking for ways of leveraging the knowledge from social networks to make their systems more personalized to their end users. And with rapid increase in the usage of mobile phones and wearables, social media data is being tied to spatial networks. This research document proposes an efficient technique that answers socially k-Nearest Neighbors with Spatial Range Filter. The proposed approach performs a joint search on both the social and spatial domains which radically improves the performance compared to straight forward solutions. The research document proposes a novel index that combines social and spatial indexes. In other words, graph data is stored in an organized manner to filter it based on spatial (region of interest) and social constraints (top-k closest vertices) at query time. That leads to pruning necessary paths during the social graph traversal procedure, and only returns the top-K social close venues. The research document then experimentally proves how the proposed approach outperforms existing baseline approaches by at least three times and also compare how each of our algorithms perform under various conditions on a real geo-social dataset extracted from Yelp.
ContributorsPasumarthy, Nitin (Author) / Sarwat, Mohamed (Thesis advisor) / Papotti, Paolo (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2016
Description
Secure Scuttlebutt is a digital social network in which the network data is distributed among the users.<br/>This is done to secure several benefits, like offline browsing, censorship resistance, and to imitate natural social networks, but it comes with downsides, like the lack of an obvious implementation of a recommendation algorithm.<br/>This paper proposes Whuffie, an algorithm that tracks each user's reputation for having information that is interesting to a user using conditional probabilities.<br/>Some errors in the main Secure Scuttlebutt network prevent current large-scale testing of the usefulness of the algorithm, but testing on my own personal account led me to believe it a success.
ContributorsVermillion, Alexander J (Author) / Bazzi, Rida (Thesis director) / Richa, Andrea (Committee member) / Computer Science and Engineering Program (Contributor) / Barrett, The Honors College (Contributor)
Created2021-05
Description
Extremal graph theory results often provide minimum degree
conditions which guarantee a copy of one graph exists within
another. A perfect $F$-tiling of a graph $G$ is a collection
$\mathcal{F}$ of subgraphs of $G$ such that every element of
$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$
is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote
the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph
obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$
on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is
uniquely assigned to $e$. This dissertation proves for even
$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$
on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree
$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +
1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect
$C^{3}_{t}$-tiling. The result is tight, generalizing previous
results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,
let the minimum color degree $\delta^c(G)$ be the minimum number of
distinctly colored edges incident to a vertex. Call $G$ rainbow if
every edge has a unique color. For $\ell \geq 5$, this dissertation
proves that any sufficiently large edge colored graph $G$ on $n$
vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow
cycle on $\ell$ vertices. The result is tight for odd $\ell$ and
extends previous results for $\ell = 3$. In addition, for even
$\ell \geq 4$, this dissertation proves that any sufficiently large
edge colored graph $G$ on $n$ vertices with
$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where
$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$
vertices. The result is tight when $6 \nmid \ell$. As a related
result, this dissertation proves for all $\ell \geq 4$, that any
sufficiently large oriented graph $D$ on $n$ vertices with
$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on
$\ell$ vertices. This partially generalizes a result by Kelly,
K\uhn" and Osthus that uses minimum semidegree rather than minimum
out degree."
conditions which guarantee a copy of one graph exists within
another. A perfect $F$-tiling of a graph $G$ is a collection
$\mathcal{F}$ of subgraphs of $G$ such that every element of
$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$
is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote
the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph
obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$
on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is
uniquely assigned to $e$. This dissertation proves for even
$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$
on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree
$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +
1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect
$C^{3}_{t}$-tiling. The result is tight, generalizing previous
results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,
let the minimum color degree $\delta^c(G)$ be the minimum number of
distinctly colored edges incident to a vertex. Call $G$ rainbow if
every edge has a unique color. For $\ell \geq 5$, this dissertation
proves that any sufficiently large edge colored graph $G$ on $n$
vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow
cycle on $\ell$ vertices. The result is tight for odd $\ell$ and
extends previous results for $\ell = 3$. In addition, for even
$\ell \geq 4$, this dissertation proves that any sufficiently large
edge colored graph $G$ on $n$ vertices with
$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where
$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$
vertices. The result is tight when $6 \nmid \ell$. As a related
result, this dissertation proves for all $\ell \geq 4$, that any
sufficiently large oriented graph $D$ on $n$ vertices with
$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on
$\ell$ vertices. This partially generalizes a result by Kelly,
K\uhn" and Osthus that uses minimum semidegree rather than minimum
out degree."
ContributorsOursler, Roy (Author) / Arizona State University (Publisher)
Created2019
Description
When looking at drawings of graphs, questions about graph density, community structures, local clustering and other graph properties may be of critical importance for analysis. While graph layout algorithms have focused on minimizing edge crossing, symmetry, and other such layout properties, there is not much known about how these algorithms relate to a user’s ability to perceive graph properties for a given graph layout. This study applies previously established methodologies for perceptual analysis to identify which graph drawing layout will help the user best perceive a particular graph property. A large scale (n = 588) crowdsourced experiment is conducted to investigate whether the perception of two graph properties (graph density and average local clustering coefficient) can be modeled using Weber’s law. Three graph layout algorithms from three representative classes (Force Directed - FD, Circular, and Multi-Dimensional Scaling - MDS) are studied, and the results of this experiment establish the precision of judgment for these graph layouts and properties. The findings demonstrate that the perception of graph density can be modeled with Weber’s law. Furthermore, the perception of the average clustering coefficient can be modeled as an inverse of Weber’s law, and the MDS layout showed a significantly different precision of judgment than the FD layout.
ContributorsSoni, Utkarsh (Author) / Maciejewski, Ross (Thesis advisor) / Kobourov, Stephen (Committee member) / Sefair, Jorge (Committee member) / Arizona State University (Publisher)
Created2018