{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72799"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72799","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Statistical inference in networks: fundamental limits and efficient algorithms","abstract":"Today witnesses an explosion of data coming from various types of networks such as online social networks and biological networks. The goal of this thesis is to understand when and how we can efficiently extract useful information from such network data. In the first part, we are interested in finding tight-knit communities within a network. Assuming the network is generated according to a planted cluster model, we derive a computationally efficient semidefinite programming relaxation of the maximum likelihood estimation method and obtain a stronger performance guarantee than previously known. If the community sizes are linear in the total number of vertices, the guarantee matches up to a constant factor with the information limit which we also identify, and exactly matches without a constant gap when there is a single community or two equal-sized communities. However, if the community sizes are sublinear in the total number of vertices, the guarantee is far from the information limit. We conjecture that our algorithm achieves the computational limit below which no polynomial-time algorithm can succeed. To provide evidence, we show that finding a community in some regime below the conjectured computational limit but above the information limit is computationally intractable, assuming hardness of the well-known planted clique problem. The second part studies the problem of inferring the group preference for a set of items based on the partial rankings over different subsets of the items provided by a group of users. A question of particular interest is how to optimally construct the graph used for assigning items to users for ranking. Assuming the partial rankings are generated independently according to the Plackett-Luce model, we analyze computationally efficient estimators based on maximum likelihood and rank-breaking schemes that decompose partial rankings into pairwise comparisons. We provide upper and lower bounds on the estimation error. The lower bound depends on the degree sequence of the assignment graph, while the upper bound depends on the spectral gap of the assignment graph. When the graph is an expander, the lower and upper bounds match up to a logarithmic factor. The unifying theme for the two parts of the thesis is the spectral gap of the graph. In both cases, when the graph has a large spectral gap, accurate and efficient inference is possible via maximum likelihood estimation or its convex relaxation. However, when the spectral gap vanishes, accurate inference may be statistically impossible, or it is statistically possible but may be computationally intractable.","abstract_html":"Today witnesses an explosion of data coming from various types of networks such as online social networks and biological networks. The goal of this thesis is to understand when and how we can efficiently extract useful information from such network data. In the first part, we are interested in finding tight-knit communities within a network. Assuming the network is generated according to a planted cluster model, we derive a computationally efficient semidefinite programming relaxation of the maximum likelihood estimation method and obtain a stronger performance guarantee than previously known. If the community sizes are linear in the total number of vertices, the guarantee matches up to a constant factor with the information limit which we also identify, and exactly matches without a constant gap when there is a single community or two equal-sized communities. However, if the community sizes are sublinear in the total number of vertices, the guarantee is far from the information limit. We conjecture that our algorithm achieves the computational limit below which no polynomial-time algorithm can succeed. To provide evidence, we show that finding a community in some regime below the conjectured computational limit but above the information limit is computationally intractable, assuming hardness of the well-known planted clique problem. The second part studies the problem of inferring the group preference for a set of items based on the partial rankings over different subsets of the items provided by a group of users. A question of particular interest is how to optimally construct the graph used for assigning items to users for ranking. Assuming the partial rankings are generated independently according to the Plackett-Luce model, we analyze computationally efficient estimators based on maximum likelihood and rank-breaking schemes that decompose partial rankings into pairwise comparisons. We provide upper and lower bounds on the estimation error. The lower bound depends on the degree sequence of the assignment graph, while the upper bound depends on the spectral gap of the assignment graph. When the graph is an expander, the lower and upper bounds match up to a logarithmic factor. The unifying theme for the two parts of the thesis is the spectral gap of the graph. In both cases, when the graph has a large spectral gap, accurate and efficient inference is possible via maximum likelihood estimation or its convex relaxation. However, when the spectral gap vanishes, accurate inference may be statistically impossible, or it is statistically possible but may be computationally intractable.","abstract_has_math":false,"creators":["Xu, Jiaming"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Hajek, Bruce","Srikant, R.","Oh, Sewoong","Sanghavi, Sujay","Lelarge, Marc"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-01-21T19:48:19Z","date_published":"2015-01-21T19:48:19Z","updated_at":"2026-07-22T22:26:07Z","subjects":["Community detection","Networks","Statistical inference"],"languages":["en"],"rights":["Copyright 2014 Jiaming Xu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/72799","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hajek, Bruce","Srikant, R.","Oh, Sewoong","Sanghavi, Sujay","Lelarge, Marc"]},{"key":"dc:creator","label":"Author","values":["Xu, Jiaming"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-01-21T19:48:19Z","2014-12","2015-01-21"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Community detection","Networks","Statistical inference"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Jiaming Xu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72799"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Today witnesses an explosion of data coming from various types of networks such as online social networks and biological networks. The goal of this thesis is to understand when and how we can efficiently extract useful information from such network data. In the first part, we are interested in finding tight-knit communities within a network. Assuming the network is generated according to a planted cluster model, we derive a computationally efficient semidefinite programming relaxation of the maximum likelihood estimation method and obtain a stronger performance guarantee than previously known. If the community sizes are linear in the total number of vertices, the guarantee matches up to a constant factor with the information limit which we also identify, and exactly matches without a constant gap when there is a single community or two equal-sized communities. However, if the community sizes are sublinear in the total number of vertices, the guarantee is far from the information limit. We conjecture that our algorithm achieves the computational limit below which no polynomial-time algorithm can succeed. To provide evidence, we show that finding a community in some regime below the conjectured computational limit but above the information limit is computationally intractable, assuming hardness of the well-known planted clique problem. The second part studies the problem of inferring the group preference for a set of items based on the partial rankings over different subsets of the items provided by a group of users. A question of particular interest is how to optimally construct the graph used for assigning items to users for ranking. Assuming the partial rankings are generated independently according to the Plackett-Luce model, we analyze computationally efficient estimators based on maximum likelihood and rank-breaking schemes that decompose partial rankings into pairwise comparisons. We provide upper and lower bounds on the estimation error. The lower bound depends on the degree sequence of the assignment graph, while the upper bound depends on the spectral gap of the assignment graph. When the graph is an expander, the lower and upper bounds match up to a logarithmic factor. The unifying theme for the two parts of the thesis is the spectral gap of the graph. In both cases, when the graph has a large spectral gap, accurate and efficient inference is possible via maximum likelihood estimation or its convex relaxation. However, when the spectral gap vanishes, accurate inference may be statistically impossible, or it is statistically possible but may be computationally intractable.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-12-05T17:13:10Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Xu_Jiaming.pdf: 768864 bytes, checksum: 6c8cb057c2d33f10fc3a17c4dbab9a9d (MD5)","Made available in DSpace on 2015-01-21T19:48:19Z (GMT). No. of bitstreams: 1 Jiaming_Xu.pdf: 768864 bytes, checksum: 6c8cb057c2d33f10fc3a17c4dbab9a9d (MD5)"]},{"key":"dc:title","label":"Title","values":["Statistical inference in networks: fundamental limits and efficient algorithms"]}]}],"canonical_facts":{"dc:contributor":["Hajek, Bruce","Srikant, R.","Oh, Sewoong","Sanghavi, Sujay","Lelarge, Marc"],"dc:creator":["Xu, Jiaming"],"dc:date":["2015-01-21T19:48:19Z","2014-12","2015-01-21"],"dc:description":["Today witnesses an explosion of data coming from various types of networks such as online social networks and biological networks. The goal of this thesis is to understand when and how we can efficiently extract useful information from such network data. In the first part, we are interested in finding tight-knit communities within a network. Assuming the network is generated according to a planted cluster model, we derive a computationally efficient semidefinite programming relaxation of the maximum likelihood estimation method and obtain a stronger performance guarantee than previously known. If the community sizes are linear in the total number of vertices, the guarantee matches up to a constant factor with the information limit which we also identify, and exactly matches without a constant gap when there is a single community or two equal-sized communities. However, if the community sizes are sublinear in the total number of vertices, the guarantee is far from the information limit. We conjecture that our algorithm achieves the computational limit below which no polynomial-time algorithm can succeed. To provide evidence, we show that finding a community in some regime below the conjectured computational limit but above the information limit is computationally intractable, assuming hardness of the well-known planted clique problem. The second part studies the problem of inferring the group preference for a set of items based on the partial rankings over different subsets of the items provided by a group of users. A question of particular interest is how to optimally construct the graph used for assigning items to users for ranking. Assuming the partial rankings are generated independently according to the Plackett-Luce model, we analyze computationally efficient estimators based on maximum likelihood and rank-breaking schemes that decompose partial rankings into pairwise comparisons. We provide upper and lower bounds on the estimation error. The lower bound depends on the degree sequence of the assignment graph, while the upper bound depends on the spectral gap of the assignment graph. When the graph is an expander, the lower and upper bounds match up to a logarithmic factor. The unifying theme for the two parts of the thesis is the spectral gap of the graph. In both cases, when the graph has a large spectral gap, accurate and efficient inference is possible via maximum likelihood estimation or its convex relaxation. However, when the spectral gap vanishes, accurate inference may be statistically impossible, or it is statistically possible but may be computationally intractable.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-12-05T17:13:10Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Xu_Jiaming.pdf: 768864 bytes, checksum: 6c8cb057c2d33f10fc3a17c4dbab9a9d (MD5)","Made available in DSpace on 2015-01-21T19:48:19Z (GMT). No. of bitstreams: 1 Jiaming_Xu.pdf: 768864 bytes, checksum: 6c8cb057c2d33f10fc3a17c4dbab9a9d (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/72799"],"dc:language":["en"],"dc:rights":["Copyright 2014 Jiaming Xu"],"dc:subject":["Community detection","Networks","Statistical inference"],"dc:title":["Statistical inference in networks: fundamental limits and efficient algorithms"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:07Z"}