Hannover, Universiẗat, Diss., 1998.

Recent advances in large graph-based models have shown great performance in a variety of tasks, including node classification, link prediction, and influence modeling. However, these graph-based models struggle to capture high-order relations and interactions among entities effectively, leading them to underperform in many real-world scenarios. This thesis focuses on analyzing networks using hypergraphs for detection, classification, and prediction methods in social media-related problems. In particular, we study four specific applications with four proposed novel methods: detecting topic-specific influential users and tweets via hypergraphs; detecting spatiotemporal, topic-specific, influential users and tweets using hypergraphs; augmenting data in hypergraphs to mitigate class imbalance issues; and introducing a novel hypergraph convolutional network model designed for the multiclass classification of mental health advice in Arabic tweets. For the first method, existing solutions for influential user detection did not consider topics that could produce incorrect results and inadequate performance in that task. The proposed contributions of our work include: 1) Developing a hypergraph framework that detects influential users and tweets. 2) Proposing an effective topic modeling method for short texts. 3) Performing extensive experiments to demonstrate the efficacy of our proposed framework. For the second method, we extend the first method by incorporating spatiotemporal information into our solution. Existing influencer detection methods do not consider spatiotemporal influencers in social media, although influence can be greatly affected by geolocation and time. The contributions of our work for this task include: 1) Proposing a hypergraph framework that spatiotemporally detects influential users and tweets. 2) Developing an effective topic modeling method for short texts that geographically provides the topic distribution. 3) Designing a spatiotemporal topic-specific influencer user ranking algorithm. 4) Performing extensive experiments to demonstrate the efficacy of our proposed framework. For the third method, we address the challenge of bot detection on social media platform X, where there's an inherent imbalance between genuine users and bots, a key factor leading to biased classifiers. Our approach leverages the rich structure of hypergraphs to represent X users and their interactions, providing a novel foundation for effective bot detection. The contributions of our work include: 1) Introducing a hypergraph representation of the X platform, where user accounts are nodes and their interactions form hyperedges, capturing the intricate relationships between users. 2) Developing HyperSMOTE to generate synthetic bot accounts within the hypergraph, ensuring a balanced training dataset while preserving the hypergraph's structure and semantics. 3) Designing a hypergraph neural network specifically for bot detection, utilizing node and hyperedge information for accurate classification. 4) Conducting comprehensive experiments to validate the effectiveness of our methods, particularly in scenarios with pronounced class imbalances. For the fourth method, we introduce a Hypergraph Convolutional Network model for classifying mental health advice in Arabic tweets. Our model distinguishes between valid and misleading advice, leveraging high-order word relations in short texts through hypergraph structures. Our extensive experiments demonstrate its effectiveness over existing methods. The key contributions of our work include: 1) Developing a hypergraph-based model for short text multiclass classification, capturing complex word relationships through hypergraph convolution. 2) Defining four types of hyperedges to encapsulate local and global contexts and semantic similarities in our dataset. 3) Conducting comprehensive experiments in which the proposed model outperforms several baseline models in classifying Arabic tweets, demonstrating its superiority. For the fifth method, we extended our previous Hypergraph Convolutional Network (HCN) model to be tailored for sarcasm detection across multiple low-resource languages. Our model excels in interpreting the subtle and context-dependent nature of sarcasm in short texts by exploiting the power of hypergraph structures to capture complex, high-order relationships among words. Through the construction of three hyperedge types, our model navigates the intricate semantic and sentiment differences that characterize sarcastic expressions. The key contributions of our research are as follows: 1) A hypergraph-based model was adapted for the task of sarcasm detection in five short low-resource language texts, allowing the model to capture semantic relationships and contextual cues through advanced hypergraph convolution techniques. 2) Introducing a comprehensive framework for constructing hyperedges, incorporating short text, semantic similarity, and sentiment discrepancy hyperedges, which together enrich the model's ability to understand and detect sarcasm across diverse linguistic contexts. 3) The extensive evaluations reveal that the proposed hypergraph model significantly outperforms a range of established baseline methods in the domain of multilingual sarcasm detection, establishing new benchmarks for accuracy and generalizability in detecting sarcasm within low-resource languages. / Doctor of Philosophy / In the digital era, social media platforms are not just tools for communication but vast networks where billions of messages, opinions, and pieces of advice are exchanged every day. Navigating through this massive data to identify influential content, detect misleading information, or understand subtle expressions like sarcasm presents a significant challenge. Traditional methods often struggle to grasp the complex relationships and nuances embedded within the data. This dissertation introduces innovative approaches using hypergraphs—a type of network representation that captures complex interactions more effectively than traditional network models. The research presented explores six distinct applications of hypergraphs in social media analysis, each addressing a unique challenge: 1) The identification of influential users and content specific to certain topics, extending beyond general influence to understand context-driven impact. 2) The incorporation of time and location to detect influential content, recognizing that relevance can significantly vary by these factors. 3) Addressing the issue of imbalanced data in bot detection, where genuine user interactions are overwhelmed by automated accounts, through novel data augmentation techniques. 4) Classifying mental health advice in Arabic tweets to differentiate between valid and misleading information is crucial, given the subject's sensitivity. 5) Detecting sarcasm in low-resource languages is particularly challenging due to its subtle and context-dependent nature. 6) Predicting metro passenger ridership at each metro station is challenging due to the constantly evolving nature of the network and passengers going in and out of stations. This work contributes to the field by demonstrating the capability of hypergraphs to provide more fine-grained and context-aware analyses of social media content. Through extensive experimentation, it showcases the effectiveness of these methods in improving detection, classification, and prediction tasks. The findings not only advance our technical understanding and capabilities in social media analysis but also have practical implications for enhancing the reliability and usefulness of information disseminated on these platforms.

Many real-world relations are networks that can be modelled with a kind of directed hypergraph named a forward hypergraph (F-graph). F-graphs capture the semantics of both conjunctive and disjunctive dependency relations. Logic statements are sometimes represented using AND/OR directed graphs and they directly correspond with F-graphs; we provide algorithms to convert between the two types of graph. One problem of interest in networks is determining the degree to which the network, with a priority on certain elements, depends upon individual nodes. We address this problem by providing an algorithm, AssetRank, which computes vertex ranks and takes into account network priorities, preferential dependencies, and extra-network influences. A second problem of interest in networks is optimizing the removal of nodes to separate two subcommunities (source and target) to the greatest practical degree, even when a complete disconnection is impractical. The problem is complicated by the need to consider the cost of removing nodes, a budget that constrains the degree to which separation is possible, cascading effects of removing a node, non-linear effects of removing nodes in combination, and removing nodes with the greatest impact on the subcommunities. To this end, we use F-graphs and introduce the concepts of vertex closures and closure-relation graphs. We created two partial-cut algorithms: the first one computes an optimal solution to this NP-hard optimization problem, and the second one estimates an optimization by exploring the closure-relation graph in a best-first search manner. Computer network defence provides a ready application area. Network defenders wish to understand which services and hosts are defence priorities (defence goals), and then, which configurations and vulnerabilities are the most useful to attackers in reaching the defence goals. The defenders' resources are constrained in terms of available person-hours, finances, and acceptable impacts to operations. The work in this thesis supports network defenders by providing actionable information that efficiently removes attack enablers and ensures defence priorities. We present an integration of our algorithms with commercial and open-source network security software. / Thesis (Ph.D, Computing) -- Queen's University, 2011-04-30 22:17:52.062

In this thesis, we introduce the intersperse coloring problem, which is a generalized version of the hypergraph coloring problem. In the intersperse coloring problem, we seek a coloring that assigns at least l different colors to each hyperedge of the input hypergraph, where l is an input parameter of the problem. We show that the notion of intersperse coloring unifies several well-known coloring problems, in addition to the conventional graph and hypergraph coloring problems, such as the strong coloring of hypergraphs, the star coloring problem, the problem of proper coloring of graph powers, the acyclic coloring problem, and the frugal coloring problem. We also provide a number of upper and lower bounds on the intersperse coloring problem on hypergraphs in the general case. The nice thing about our general bounds is that they can be applied to all the coloring problems that are special cases of the intersperse coloring problem. In this thesis, we also propose a new model for graph and hypergraph property testing, called the symmetric model. The symmetric model is the first model that can be used for developing property testing algorithms for non-uniform hypergraphs. We also prove that there exist graph properties that have efficient property testers in the symmetric model but do not have any efficient property tester in previously-known property testing models.

In this thesis, we introduce the intersperse coloring problem, which is a generalized version of the hypergraph coloring problem. In the intersperse coloring problem, we seek a coloring that assigns at least l different colors to each hyperedge of the input hypergraph, where l is an input parameter of the problem. We show that the notion of intersperse coloring unifies several well-known coloring problems, in addition to the conventional graph and hypergraph coloring problems, such as the strong coloring of hypergraphs, the star coloring problem, the problem of proper coloring of graph powers, the acyclic coloring problem, and the frugal coloring problem. We also provide a number of upper and lower bounds on the intersperse coloring problem on hypergraphs in the general case. The nice thing about our general bounds is that they can be applied to all the coloring problems that are special cases of the intersperse coloring problem. In this thesis, we also propose a new model for graph and hypergraph property testing, called the symmetric model. The symmetric model is the first model that can be used for developing property testing algorithms for non-uniform hypergraphs. We also prove that there exist graph properties that have efficient property testers in the symmetric model but do not have any efficient property tester in previously-known property testing models.

A mixed hypergraph is a triple H = (X; C;D), where X is the vertex set, and each of C;D is a list of subsets of X. A strict t-coloring is a onto mapping from X to {1, 2,…,t} such that each c belongs to C contains two vertices have a common value and each d belongs to D has two vertices have distinct values. If H has a strict t-coloring, then t belongs to S(H), such S(H) is called the feasible set of H, and k is a gap if there are a value larger than k and a value less than k in the feasible set but k is not. We find the minimum and maximum gap of a mixed hypergraph with more than 5 vertices. Then we consider two special cases of the gap of mixed hypergraphs. First, if the mixed hypergraphs is spanned by a complete bipartite graph, then the gap is decided by the size of bipartition. Second, the (l,m)-uniform mixed hypergraphs has gaps if l > m/2 >2, and we prove that the minimum number of vertices of a (l,m)-uniform mixed hypergraph which has gaps is (m/2)( l -1) + m.

Berlin, Freie University, Diss., 2004. / Dateiformat: zip, Dateien im PDF-Format.

The search for max-cliques in graphs is a well established NP-complete problem in graph theory and algorithm design, with many algorithms designed to make use of internal structures of specific types of graphs. We study the extension of the problem of searching for max-cliques in graphs to hypergraphs with constant edge size k, and adapt existing algorithms for graphs to work in k-hypergraphs. In particular, we are interested in the generalization of circulant graphs to circulant k-hypergraphs, and provide a definition of this type of hypergraph. We design and implement a new algorithm to perform max-clique searches on circulant k-hypergraphs. This algorithm combines ideas from a Russian doll algorithm for max-cliques in graphs (Ostergard 2002) with an algorithm based on necklaces for a class of circulant k-hypergraphs (Tzanakis, Moura, Stevens and Panario 2016). We examine the performance of our new algorithm against a set of adapted algorithms (backtracking and Russian doll search for general k-hypergraphs, and necklace-based search for circulant k-hypergraphs) in a set of benchmarking experiments across various densities and edge sizes. This study reveals that the new algorithm outperforms the others when edge density of the hypergraph is high, and that the pure necklace-based algorithm is best in the case of low densities. Finally, we use our new algorithm to perform an exhaustive search on circulant 4-hypergraphs constructed from linear feedback shift register sequences on finite fields of order q that yields covering arrays. The search is completed for 2 <= q <= 5 which solves the open case of q=5 left by Tzanakis et al.

(l,m)-uniform混和超級圖的色譜一定是是連續的, 利用一個技巧讓所有l大於二的(l,m)-uniform混和超級圖都存在一組C-edges 和 D-edges, 使得光譜不連續.最後提供一個演算法, 讓所有l和m 都大於二的(l,m)-uniform混和超級圖, 也存在一組 C-edges 和 D-edges, 使得光譜不連續. 這樣我們就已經討論完所有(l,m)-uniform混和超級圖( l , m 都要大於等於 2), 其光譜是否存在著有不連續的可能. / In this thesis, we study all existences of gap in every kind of (l,m)-uniform mixed hypergraph, where n > 1 and m > 1. We have to divide the topic into three parts: (2,m)-uniform mixed hypergraph where m > 1, (l,2)-uniform mixed hypergraph where l > 2, and (l,m)-uniform mixed hypergraph where l > 2 and m > 2.

This thesis proposes a link-based approach to identify supporting and opposing groups in a Weblog community. We formulate the interaction behavior as a graph. Bloggers involved in the discussion of one specific issue are formulated as vertices. Semantic orientation is used to construct possible opposite opinion links. Bloggers with opposite stances will form an opposite link. A max-cut algorithm is used latter to obtain the optimal approximation of supporting and opposing groups. The categorization results are compared between semantic orientation classifier and simple link-based categorization. The simple link-based categorization compares then with the enhancement of link-based categorization using hypergraph.