Search

Manual debugging is notoriously tedious and time consuming. Therefore, various automated fault localization techniques have been proposed to help with manual debugging. Among the existing fault localization techniques, spectrum-based fault localization (SBFL) is one of the most widely studied techniques due to being lightweight. A focus of existing SBFL techniques is to consider how to differentiate program source code entities (i.e., one dimension in program spectra); indeed, this focus is aligned with the ultimate goal of finding the faulty lines of code. Our key insight is to enhance existing SBFL techniques by additionally considering how to differentiate tests (i.e., the other dimension in program spectra), which, to the best of our knowledge, has not been studied in prior work. We present PRFL, a lightweight technique that boosts spectrum-based fault localization by differentiating tests using PageRank algorithm. Given the original program spectrum information, PRFL uses PageRank to recompute the spectrum information by considering the contributions of different tests. Then, traditional SBFL techniques can be applied on the recomputed spectrum information to achieve more effective fault localization. Although simple and lightweight, PRFL has been demonstrated to outperform state-of-the-art SBFL techniques significantly (e.g., ranking 42% more real faults within Top-1 compared with the most effective traditional SBFL technique) with low overhead (e.g., around 2 minute average extra overhead on real faults) on 332 real faults from 5 Defects4J projects and 30692 artificial (i.e., mutation) faults from 87 GitHub projects, demonstrating a promising future for considering the contributions of different tests during fault localization.

The use of social network analysis in physics education research seeks to advanceunderstanding of how students’ collaborative tendencies influence trends of learning.Common useful measurements are network size, density of connections, and centralitymeasures that describe the importance of nodes’ positions. This study compared fourdifferent centrality measures at the beginning and end of seven sections of an introductorycalculus-based physics course. The Force Concept Inventory was used as a measure ofconceptual learning at pre- and post-course administrations. The main focus of this studywas to identify if differences in network centralities and conceptual learning/knowledgeexist with respect to students’ designations as non-traditional or traditional (age 22+).Various class sizes, styles, and instructors were included in the data. Results showedsome common and conflicting trends for the different class types, with non-traditionalstudents generally at a disadvantage in network position but comparable in conceptualscores.

Massive social networks have become increasingly popular in recent years. Community detection is one of the most important techniques for the analysis of such complex networks. A community is a set of cohesive vertices that has more connections inside the set than outside. In many social and information networks, these communities naturally overlap. For instance, in a social network, each vertex in a graph corresponds to an individual who usually participates in multiple communities. In this thesis, we propose scalable overlapping community detection algorithms that effectively identify high quality overlapping communities in various real-world networks. We first develop an efficient overlapping community detection algorithm using a seed set expansion approach. The key idea of this algorithm is to find good seeds and then greedily expand these seeds using a personalized PageRank clustering scheme. Experimental results show that our algorithm significantly outperforms other state-of-the-art overlapping community detection methods in terms of run time, cohesiveness of communities, and ground-truth accuracy. To develop more principled methods, we formulate the overlapping community detection problem as a non-exhaustive, overlapping graph clustering problem where clusters are allowed to overlap with each other, and some nodes are allowed to be outside of any cluster. To tackle this non-exhaustive, overlapping clustering problem, we propose a simple and intuitive objective function that captures the issues of overlap and non-exhaustiveness in a unified manner. To optimize the objective, we develop not only fast iterative algorithms but also more sophisticated algorithms using a low-rank semidefinite programming technique. Our experimental results show that the new objective and the algorithms are effective in finding ground-truth clusterings that have varied overlap and non-exhaustiveness. We extend our non-exhaustive, overlapping clustering techniques to co-clustering where the goal is to simultaneously identify a clustering of the rows as well as the columns of a data matrix. As an example application, consider recommender systems where users have ratings on items. This can be represented by a bipartite graph where users and items are denoted by two different types of nodes, and the ratings are denoted by weighted edges between the users and the items. In this case, co-clustering would be a simultaneous clustering of users and items. We propose a new co-clustering objective function and an efficient co-clustering algorithm that is able to identify overlapping clusters as well as outliers on both types of the nodes in the bipartite graph. We show that our co-clustering algorithm is able to effectively capture the underlying co-clustering structure of the data, which results in boosting the performance of a standard one-dimensional clustering. Finally, we study the design of parallel data-driven algorithms, which enables us to further increase the scalability of our overlapping community detection algorithms. Using PageRank as a model problem, we look at three algorithm design axes: work activation, data access pattern, and scheduling. We investigate the impact of different algorithm design choices. Using these design axes, we design and test a variety of PageRank implementations finding that data-driven, push-based algorithms are able to achieve a significantly superior scalability than standard PageRank implementations. The design choices affect both single-threaded performance as well as parallel scalability. The lessons learned from this study not only guide efficient implementations of many graph mining algorithms but also provide a framework for designing new scalable algorithms, especially for large-scale community detection.

Our unprecedented capacity for data generation and acquisition often reaches the limits of our data storage capabilities. Situations when data are generated faster or at a greater volume than can be stored demand a streaming approach. Memory is an even more valuable resource. Algorithms that use more memory than necessary can pose bottlenecks when processing high-dimensional data and the need for memory-efficient algorithms is especially stressed in the streaming setting. Finally, network along with storage, emerge as the critical bottlenecks in the context of distributed computation. These computational constraints spell out a demand for efficient tools that guarantee a solution in the face of limited resources, even when the data is very noisy or highly incomplete. For the first part of this dissertation, we present our work on streaming, memory-limited Principal Component Analysis (PCA). Therein, we give the first convergence guarantees for an algorithm that solves PCA in the single-pass streaming setting. Then, we discuss the distinct challenges that arise when the received samples are overwhelmingly incomplete and present an algorithm and analysis that deals with this issue. Finally, we give a set of extensive experiment results that showcase the practical merits of our algorithm over the state of the art. The need for heavy network communication arises as the bottleneck when dealing with cluster computation. In that paradigm, a set of worker nodes are connected over the network to produce a cluster with improved computational and storage capacities. This comes with an increased need for communication across the network. In the last part of this work, we consider the problem of PageRank on graph engines. Therein, we make changes to GraphLab, a state-of-the-art platform for distributed graph computation, in a way that leads to a 7x-10x speedup for certain PageRank approximation tasks. Accompanying analysis supports the behaviour we see in our experiments.

As Internet communities such as question-answer (Q&A) forums and online social networks (OSNs) grow in prominence as knowledge sources, traditional editorial filters are unable to scale to their size and pace. This absence hinders the exchange of knowledge online, by creating an understandable lack of trust in information. This mistrust can be partially overcome by a forum by consistently providing reliable information, thus establishing itself as a reliable source. This work investigates how algorithmic approaches can contribute to building such a community of voluntary experts willing to contribute authoritative information. This work identifies two approaches: a) reducing the cost of participation for experts via matching user queries to experts (question recommendation), and b) identifying authoritative contributors for incentivization (authority estimation). The question recommendation problem is addressed by extending existing approaches via a new generative model that augments textual data with expert preference information among different questions. Another contribution to this domain is the introduction of a set of formalized metrics to include the expert's experience besides the questioner's. This is essential for expert retention in a voluntary community, and has not been addressed by previous work. The authority estimation problem is addressed by observing that the global graph structure of user interactions, results from two factors: a user's performance in local one-to-one interactions, and their activity levels. By positing an intrinsic authority 'strength' for each user node in the graph that governs the outcome of individual interactions via the Bradley-Terry model for pairwise comparison, this research establishes a relationship between intrinsic user authority, and global measures of influence. This approach overcomes many drawbacks of current measures of node importance in OSNs by naturally correcting for user activity levels, and providing an explanation for the frequent disconnect between real world reputation and online influence. Also, while existing research has been restricted to node ranking on a single OSN graph, this work demonstrates that co-ranking across multiple endorsement graphs drawn from the same OSN is a highly effective approach for aggregating complementary graph information. A new scalable co-ranking framework is introduced for this task. The resulting algorithms are evaluated on data from various online communities, and empirically shown to outperform existing approaches by a large margin.

This thesis sets out to articulate a theory and method for criticism of ethico-politico-aesthetic conjunctions in what has been termed a ‘post-hegemonic’ and ‘post-modern’ ‘digital age’. It begins by making the case for the use of affect theory by demonstrating the capacity for political agency in affective transductions to, from, and amongst the masses. While many declared the death of rationality and linguistic communication, and from this declaration concluded that the inertia of the masses would eventually lead to an implosion, I argue that politics is alive and well at the level of affective transduction, and thus operative below, between, or alongside linguistic and rational exchanges. I further argue that the need for a rigorous theory and methodology for affect is made more urgent by the catalysis of affective transduction brought about by the rise of the digital. As such, I set out to develop a methodology for criticizing such affective transductions and then to apply this theory and methodology to concrete cases. In particular, I attempt to correct the current trajectory of scholarly appropriation of affect theory by pointing out ontological misconstructions. Having developed an ontologically sound articulation of affect, I set out to apply it to the case of the revolutionary and the capitalist. In the case of the revolutionary, I attempt to provide a rigorous defense of the popular assertion that affective production must always occur externally to capital, and can only then be appropriated afterwards. I show that the necessarily fiscally damaging and unscrupulous aspects of affective engineering defy commodity fetishism, the operative logic of capital, and thus that capital, even if it were capable of engineering affects, would have no interest in doing so. For capital, I trace the way in which affective refrains are continually systematized, rigidified, and deployed by capitalist structures in a normative fashion. In particular, I look at the case of Google search to demonstrate the ways in which control structures disseminate refrains in such a way that bodies become increasingly stratified and bounded. In closing, I suggest theoretical and practical areas of affect in need of future development.

Keyphrases describe a document in a coherent and simple way, giving the prospective reader a way to quickly determine whether the document satisfies their information needs. The pervasion of huge amount of information on Web, with only a small amount of documents have keyphrases extracted, there is a definite need to discover automatic keyphrase extraction systems. Typically, a document written by human develops around one or more general concepts or sub-concepts. These concepts or sub-concepts should be structured and semantically related with each other, so that they can form the meaningful representation of a document. Considering the fact, the phrases or concepts in a document are related to each other, a new approach for keyphrase extraction is introduced that exploits the semantic relations in the document. For measuring the semantic relations between concepts or sub-concepts in the document, I present a comprehensive study aimed at using collaboratively constructed semantic resources like Wikipedia and its link structure. In particular, I introduce a graph-based keyphrase extraction system that exploits the semantic relations in the document and features such as term frequency. I evaluated the proposed system using novel measures and the results obtained compare favorably with previously published results on established benchmarks.

This dissertation concerns itself with creating a new algorithm for automatically measuring the amount of relatedness between a given pair of terms. Research into term relatedness is important because it has been empirically demonstrated that using relatedness metrics can improve the performance of tasks in Natural Language Processing and Information Retrieval by expanding the usable vocabulary. Previous relatedness metrics have used a variety of sources of semantic data to judge term relatedness, including text corpora, expertly-constructed resources and, most recently, Wikipedia and Wiktionary. The primary focus of this dissertation is the creation of a new metric for deriving term relatedness from the graph structure of Wikipedia and Wiktionary using Sourced PageRank, a modified version of the PageRank algorithm, to generate the relatedness values.This new algorithm is compared to several existing relatedness metrics in two established task domains. The first domain measures the metric’s ability to replicate human-generated relatedness values for term pairs. The second domain tests a metric’s ability to select the synonym of a given term from a list of possible candidates. In both of these experiments, the Sourced PageRank-based term relatedness algorithm that uses Wiktionary as its source of semantic data is able to compete with or exceed the performance of existing state-of-the-art algorithms in these task domains.Additionally, the different emphases of Wikipedia and Wiktionary are covered as part of this dissertation. This is an area that has not been emphasized in past work with Wiki-based relatedness metrics. We find that Wikipedia is a source of information on proper names and their real-world referents, including corporations, events and people. Wiktionary has more information on common words that almost everyone knows. Each Wiki-based resource has its own strength and must be matched with the needs of the task in order to yield maximum benefits.Finally, we explore how to use additional information found in Wikipedia and Wiktionary as meta-data for graph manipulation. While we achieve mixed results, the investigation opens another area of research for graph-based relatedness metrics that use Wikipedia or Wiktionary as the source of semantic data.

This dissertation describes WikiRank, an unsupervised method of assigning relative values to elements of a broad coverage encyclopedic information source in order to identify those entries that may be relevant to a given piece of text. The valuation given to an entry is based not on textual similarity but instead on the links that associate entries, and an estimation of the expected frequency of visitation that would be given to each entry based on those associations in context. This estimation of relative frequency of visitation is embodied in modifications to the random walk interpretation of the PageRank algorithm. WikiRank is an effective algorithm to support natural language processing applications. It is shown to exceed the performance of previous machine learning algorithms for the task of automatic topic identification, providing results comparable to that of human annotators. Second, WikiRank is found useful for the task of recognizing text-based paraphrases on a semantic level, by comparing the distribution of attention generated by two pieces of text using the encyclopedic resource as a common reference. Finally, WikiRank is shown to have the ability to use its base of encyclopedic knowledge to recognize terms from different ontologies as describing the same thing, and thus allowing for the automatic generation of mapping links between ontologies. The conclusion of this thesis is that the "knowledge access heuristic" is valuable and that a ranking process based on a large encyclopedic resource can form the basis for an extendable general purpose mechanism capable of identifying relevant concepts by association, which in turn can be effectively utilized for enumeration and comparison at a semantic level.

Some of the theory of nonnegative matrices is first presented. The Perron-Frobenius theorem is highlighted. Some of the important linear algebraic methods of information retrieval are surveyed. Latent Semantic Indexing (LSI), which uses the singular value de-composition is discussed. The Hyper-Text Induced Topic Search (HITS) algorithm is next considered; here the power method for finding dominant eigenvectors is employed. Through the use of a theorem by Sinkohrn and Knopp, a modified HITS method is developed. Lastly, the PageRank algorithm is discussed. Numerical examples and MATLAB programs are also provided.

The computation of economic equilibria is a central problem in algorithmic game theory. In this dissertation, we investigate the existence of economic equilibria in several markets and games, the complexity of computing economic equilibria, and its application to rankings. It is well known that a competitive economy always has an equilibrium under mild conditions. In this dissertation, we study the complexity of computing competitive equilibria. We show that given a competitive economy that fully respects all the conditions of Arrow-Debreu's existence theorem, it is PPAD-hard to compute an approximate competitive equilibrium. Furthermore, it is still PPAD-Complete to compute an approximate equilibrium for economies with additively separable piecewise linear concave utility functions. Degeneracy is an important concept in game theory. We study the complexity of deciding degeneracy in games. We show that it is NP-Complete to decide whether a bimatrix game is degenerate. With the advent of the Internet, an agent can easily have access to multiple accounts. In this dissertation we study the path auction game, which is a model for QoS routing, supply chain management, and so on, with multiple edge ownership. We show that the condition of multiple edge ownership eliminates the possibility of reasonable solution concepts, such as a strategyproof or false-name-proof mechanism or Pareto efficient Nash equilibria. The stationary distribution (an equilibrium point) of a Markov chain is widely used for ranking purposes. One of the most important applications is PageRank, part of the ranking algorithm of Google. By making use of perturbation theories of Markov chains, we show the optimal manipulation strategies of a Web spammer against PageRank under a few natural constraints. Finally, we make a connection between the ranking vector of PageRank or the Invariant method and the equilibrium of a Cobb-Douglas market. Furthermore, we propose the CES ranking method based on the Constant Elasticity of Substitution (CES) utility functions.

We present two different views of (row) stochastic matrices, which are nonnegative matrices with row sums equal to one. For applications to ranking, we examine the computation of a dominant left eigenvector of a stochastic matrix. The stochastic matrix of interest is called the Google matrix and contains information about how pages of the Internet are linked to one another. The dominant left eigenvector of the Google matrix yields a ranking for each Web page, which helps to determine the order in which search results are returned. These results are presented in Chapter 1. Chapter 2 is concerned with coefficients of ergodicity, which measure the rate at which products of stochastic matrices, especially products whose number of factors is unbounded, converge to a matrix of rank one. Ergodicity arises in the context of Markov chains and signals the tendency of the rows of such products to equalize. We present unified notation and definitions for coefficients of ergodicity applied to stochastic matrices, extend the definitions to general complex matrices, and illustrate the connection between ergodicity coefficients and inclusion regions for eigenvalues and singular values.

The PageRank algorithm, developed by Google founders Larry Page and Sergey Brin, assigns ranking scores to webpages that reflect their relative importance. These scores are based primarily on the link structure of the Web graph and correspond to elements of a dominant left eigenvector, called the PageRank vector, of the stochastic Google matrix. When the starting vector is a probability vector, the iterates of the power method applied to the Google matrix converge to the PageRank vector. Determining when to stop the iterations requires deciding when an iterate vector is good enough. Existing termination criteria rely on various measures of distance between successive iterate vectors. In this dissertation, we investigate how well a power method iterate vector approximates the PageRank vector, we show that the existing termination criteria do not guarantee accurate ranking, and we provide a computationally efficient criterion for determining relative rankings, exact rankings, and ranking intervals of PageRank scores.

Developing, maintaining, and disseminating trust in open environments is crucial. We develop a decentralized approach to trust in the context of service location. Service providers and consumers are modeled as autonomous agents participating in a multiagent system that functions as a referral network. When a service is requested, an agent may provide the requested service or give a referral to another agent. The agents can judge the quality of service obtained. Importantly the agents can adaptively select their neighbors, decide with whom to interact, and choose how to give referrals. The agents' actions lead to the evolution of the referral network. We study the emergent properties of referral networks, especially those dealing with their quality, efficiency, and structure. We first show how the exchange of referrals affect locating service providers, then identify undesirable network structures and show under which conditions these network structures emerge. A referral corresponds to a customized link generated on demand by one agent for another. Referrals thus yield a basis for studying the processes underlying trust and authority, especially as they affect the structure of the evolving social network of agents. Whereas existing work takes an after-the-fact look at Web structure, we can study the emergence of structure as it relates to the policies of the members. Further, we propose a graph-based representation of services that can be applied in conjunction with our referrals-based approach. This representation captures natural relationships among service domains and provides a simple means to accommodate the accrual of trust placed in a given party. Using this representation we study how number of interactions and ease at which agents try new providers affect locating trustworthy providers. The properties uncovered through this dissertation can serve as guidelines to develop robust referral systems that are both efficient and effective.