{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-8169"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-8169","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Lost In The Crowd: Are Large Social Graphs Inherently Indistinguishable?","abstract":"Real social graphs datasets are fundamental to understanding a variety of phenomena, such as epidemics, crowd management and political uprisings, yet releasing digital recordings of such datasets exposes the participants to privacy violations. A safer approach to making real social network topologies available is to anonymize them by modifying the graph structure enough as to decouple the node identity from its social ties, yet preserving the graph characteristics in aggregate. At scale, this approach comes with a significant challenge in computational complexity. This thesis questions the need to structurally anonymize very large graphs. Intuitively, the larger the graph, the easier for an individual to be “lost in the crowd”. On the other hand, at scale new topological structures may emerge, and those can expose individual nodes in ways that smaller structures do not. To answer this problem, this work introduces a set of metrics for measuring the indistinguishability of nodes in large-scale social networks independent of attack models and shows how different graphs have different levels of inherent indistinguishability of nodes. Moreover, we show that when varying the size of a graph, the inherent node indistinguishability decreases with the size of the graph. In other words, the larger a graph of a graph structure, the higher the indistinguishability of its nodes.","abstract_html":"Real social graphs datasets are fundamental to understanding a variety of phenomena, such as epidemics, crowd management and political uprisings, yet releasing digital recordings of such datasets exposes the participants to privacy violations. A safer approach to making real social network topologies available is to anonymize them by modifying the graph structure enough as to decouple the node identity from its social ties, yet preserving the graph characteristics in aggregate. At scale, this approach comes with a significant challenge in computational complexity. This thesis questions the need to structurally anonymize very large graphs. Intuitively, the larger the graph, the easier for an individual to be “lost in the crowd”. On the other hand, at scale new topological structures may emerge, and those can expose individual nodes in ways that smaller structures do not. To answer this problem, this work introduces a set of metrics for measuring the indistinguishability of nodes in large-scale social networks independent of attack models and shows how different graphs have different levels of inherent indistinguishability of nodes. Moreover, we show that when varying the size of a graph, the inherent node indistinguishability decreases with the size of the graph. In other words, the larger a graph of a graph structure, the higher the indistinguishability of its nodes.","abstract_has_math":false,"creators":["Vadamalai, Subramanian Viswanathan"],"institution":"University of South Florida","degree_name":"MS in Computer Science (M.S.C.S.)","degree_level":"Thesis","degree_discipline":"Computer Science and Engineering","degree_department":null,"school":null,"contributors":["Adriana Iamnitchi, Ph.D.","John Skvoretz, Ph.D.","Paul Rosen, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-06-19T07:00:00Z","date_published":"2017-06-19T07:00:00Z","updated_at":"2026-11-19T08:43:17Z","subjects":["Graph Anonymization","Privacy Metric","Linkage Covariance","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/6972","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/6972","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-8169","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Adriana Iamnitchi, Ph.D.","John Skvoretz, Ph.D.","Paul Rosen, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Vadamalai, Subramanian Viswanathan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-06-19T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","M.S.C.S."]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Computer Science (M.S.C.S.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Anonymization","Privacy Metric","Linkage Covariance","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/6972"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Real social graphs datasets are fundamental to understanding a variety of phenomena, such as epidemics, crowd management and political uprisings, yet releasing digital recordings of such datasets exposes the participants to privacy violations. A safer approach to making real social network topologies available is to anonymize them by modifying the graph structure enough as to decouple the node identity from its social ties, yet preserving the graph characteristics in aggregate. At scale, this approach comes with a significant challenge in computational complexity. This thesis questions the need to structurally anonymize very large graphs. Intuitively, the larger the graph, the easier for an individual to be “lost in the crowd”. On the other hand, at scale new topological structures may emerge, and those can expose individual nodes in ways that smaller structures do not. To answer this problem, this work introduces a set of metrics for measuring the indistinguishability of nodes in large-scale social networks independent of attack models and shows how different graphs have different levels of inherent indistinguishability of nodes. Moreover, we show that when varying the size of a graph, the inherent node indistinguishability decreases with the size of the graph. In other words, the larger a graph of a graph structure, the higher the indistinguishability of its nodes."]},{"key":"dc:title","label":"Title","values":["Lost In The Crowd: Are Large Social Graphs Inherently Indistinguishable?"]}]}],"canonical_facts":{"dc:contributor":["Adriana Iamnitchi, Ph.D.","John Skvoretz, Ph.D.","Paul Rosen, Ph.D."],"dc:creator":["Vadamalai, Subramanian Viswanathan"],"dc:date":["2017-06-19T07:00:00Z"],"dc:description":["Real social graphs datasets are fundamental to understanding a variety of phenomena, such as epidemics, crowd management and political uprisings, yet releasing digital recordings of such datasets exposes the participants to privacy violations. A safer approach to making real social network topologies available is to anonymize them by modifying the graph structure enough as to decouple the node identity from its social ties, yet preserving the graph characteristics in aggregate. At scale, this approach comes with a significant challenge in computational complexity. This thesis questions the need to structurally anonymize very large graphs. Intuitively, the larger the graph, the easier for an individual to be “lost in the crowd”. On the other hand, at scale new topological structures may emerge, and those can expose individual nodes in ways that smaller structures do not. To answer this problem, this work introduces a set of metrics for measuring the indistinguishability of nodes in large-scale social networks independent of attack models and shows how different graphs have different levels of inherent indistinguishability of nodes. Moreover, we show that when varying the size of a graph, the inherent node indistinguishability decreases with the size of the graph. In other words, the larger a graph of a graph structure, the higher the indistinguishability of its nodes."],"dc:identifier":["https://digitalcommons.usf.edu/etd/6972"],"dc:subject":["Graph Anonymization","Privacy Metric","Linkage Covariance","Computer Sciences"],"dc:title":["Lost In The Crowd: Are Large Social Graphs Inherently Indistinguishable?"],"thesis:degree_discipline":["Computer Science and Engineering"],"thesis:degree_level":["Thesis","M.S.C.S."],"thesis:degree_name":["MS in Computer Science (M.S.C.S.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:43:17Z"}