Search

Graphs, also known as networks, are an expressive data representation used in many domains. Numerous algorithms have been designed to find interesting patterns in graphs. However, they have at least one of two major drawbacks. First, most algorithms focus on finding complex subgraphs but ignore relationships between attributes. But attributes play a major role in several real-life applications such as for profile completion in social networks. Second, the user must generally set multiple parameters that greatly influence results but are unintuitive to set. To provide a solution to these issues, this paper introduces a novel algorithm named CSPM (Compressing Star Pattern Miner) for discovering compressing patterns in an attributed graph. The algorithm is parameter-free and discovers star-shaped attribute patterns that reveal strong relationships between attribute values by utilizing the concept of conditional entropy and the minimum description length principle. Extensive experiments on real data show that CSPM is efficient and can find insightful patterns. In particular, it is observed that the discovered patterns can boost the accuracy of state-of-the-art graph attribute completion models on social network databy up to 15.39%. Moreover, it is found that CSPM can uncover many interesting patterns describing alarm correlations in data from a large-scale industrial telecommunication network. [ABSTRACT FROM AUTHOR]

PageRank is a classic measure that effectively evaluates the importance of nodes in large graphs. It has been applied in numerous applications spanning data mining, Web algorithms, recommendation systems, load balancing, search and connectivity structures identification. Computing PageRank for large graphs is challenging and this has motivated the studies of distributed algorithms to compute PageRank. Previously, little works have been spent on the distributed PageRank algorithms with strong guarantees on both complexity and accuracy. In this paper, we focus on the theoretical aspect and study the complexity of distributed PageRank computation based on the well-known congested-clique model with a bandwidth generalization. An existing algorithm proposed by Sarma et al. (2015) can be applied in this model, which estimates PageRanks in an n -node graph using, with high probability, O (log n) communication rounds and a bandwidth of O ((log n) 3) bits. We present Radar-Push (RP), which is a distributed PageRank algorithm that is strictly better in round complexities. Specifically, Radar-Push uses O (log log n) communication rounds and an edge bandwidth of O ((log n) 3) bits. We further show that Radar-Push can be adapted to efficiently compute an important variant of PageRank, namely, the batch one-hop personalized PageRank, in O (log log n) communication rounds. [ABSTRACT FROM AUTHOR]

The success of fuzzy clustering relies heavily on the features of the input data. However, traditional fuzzy clustering methods focus on primitive features that represent the physical properties of data, such as the shape and color of objects. Usually, these properties could only capture the local distribution of data, while ignoring the global structure of data. Fortunately, by performing spectral analysis on the similarity graph of data, spectral clustering methods explore more on the global structure. However, capturing a decent global structure by constructing an ideal similarity graph is not easy. In this paper, we propose a novel fuzzy clustering method, the bilevel fuzzy clustering via adaptive similarity graphs fusion (BFCS), to solve the problems mentioned above at the same time. On the one hand, the global data structure is investigated by building an adaptive similarity graph using autoweighted fusion. On the other hand, the consistent memberships for both fuzzy clustering and spectral clustering are formulated into one objective function to simultaneously retain the local physical properties and the global data structure. Notably, the proposed method shows good scalability, and the bilevel structure of the algorithm makes its application to large datasets easy. Extensive experiments demonstrate the promising clustering performance of the proposed BFCS on synthetic and real datasets. [ABSTRACT FROM AUTHOR]

The flexible paradigm of the Resource Description Framework (RDF) has accelerated the rate at which raw data is published on the web. Therefore, the volume of generated RDF data has increased impressively in the last decade, which promotes the use of compression to manage and reduce the size of RDF datasets. Furthermore, researchers have recently tried to reconstruct convolution and pooling procedures to better suit the structure of graphs and make convolutional neural networks (CNNs) more applicable to RDF graph data. In this study, we propose the Multi Kernel Inductive RDF Graph Convolution Network (MKIR-GCN), which, rather than compressing nodes/edges independently, uses similarities between nodes and the structure of graphs to reduce the size of all nodes and edges simultaneously to efficiently compress the RDF graph. By considering the topology and similarity of a network's nodes, our proposed attention based on similarity for RDF graph pooling (ASGPool) picks the most informative and representative nodes. In dynamic graphs, our proposed MKIR-GCN layer may learn more generic node representations by focusing on diverse characteristics. Through extensive experimentation, we can conclude that the proposed approach significantly improves compression over the existing graph representation learning schemes and RDF graph compression schemes. [ABSTRACT FROM AUTHOR]

Graph-based regularized nonnegative matrix factorization (NMF) methods performed well in many real-world applications. However, it is still an open problem to construct an optimal graph to effectively discover the intrinsic geometric structure of data. In this paper, we propose a new data representation framework, called rank-constrained nonnegative matrix factorization (RCNMF). We impose the rank constraint on the Laplacian matrix of the learned graph, so it can ensure that the number of connected components is consistent with the number of sample categories. Instead of a fixed graph-based regularization, the proposed framework can adaptively adjust the weight of the affinity matrix in each iteration. We develop two versions of RCNMF based on the l 1 and l 2 norms, and introduce their optimization schemes. In addition, their convergence and the complexity analyses are also provided. Experimental results on four benchmark datasets show that our methods outperform state-of-the-art methods in clustering. [ABSTRACT FROM AUTHOR]

A new distance in finite graphs is defined through a game-theoretic approach. This distance arises when solving the problem about the fair cost, for a node in a graph, of attaining access to another node. The distance indicates the level of difficulty in the communication between any pair of nodes, on the understanding that the fewer paths there are between two nodes and the more nodes there are that form those paths, the greater the distance is. [ABSTRACT FROM AUTHOR]

The study and analysis of social graphs impacts on a wide range of applications, such as community decision making support and recommender systems. With the boom of online social networks, such analyses are benefiting from a massive collection and publication of social graphs at large scale. Unfortunately, individuals’ privacy right might be inadvertently violated when publishing this type of data. In this article, we introduce ( k , ℓ)-anonymity; a novel privacy measure aimed at evaluating the resistance of social graphs to active attacks. ( k , ℓ)-anonymity is based on a new problem in Graph Theory, the k-metric antidimension defined as follows. Let G = ( V , E ) be a simple connected graph and S = { w 1 , … , w t } ⊆ V an ordered subset of vertices. The metric representation of a vertex u ∈ V with respect to S is the t -vector r ( u | S ) = ( d G ( u , w 1 ) , … , d G ( u , w t ) ) , where d G ( u, v ) represents the length of a shortest u − v path in G . We call S a k -antiresolving set if k is the largest positive integer such that for every vertex v ∈ V − S there exist other k − 1 different vertices v 1 , … , v k − 1 ∈ V − S with r ( v | S ) = r ( v 1 | S ) = ⋯ = r ( v k − 1 | S ) . The k -metric antidimension of G is the minimum cardinality among all the k -antiresolving sets for G . We address the k -metric antidimension problem by proposing a true-biased algorithm with success rate above 80% when considering random graphs of size at most 100. The proposed algorithm is used to determine the privacy guarantees offered by two real-life social graphs with respect to ( k , ℓ)-anonymity. We also investigate theoretical properties of the k -metric antidimension of graphs. In particular, we focus on paths, cycles, complete bipartite graphs and trees. [ABSTRACT FROM AUTHOR]

Existing studies on graph-based analysis focus on standard graphs that are precise and complete. However, in many prevalent application domains, such as social, biological, and mobile networks, the existence of an edge in a graph is best captured by a likelihood measure or a probability. This paper investigates the problem of node similarity computation on large uncertain graphs. We first extend the well-known SimRank to define meaningful similarity measure on probabilistic graphs, and then propose a probabilistic framework to compute it. Based on the observation that the probabilistic transition probabilities computed on the whole graph equal to those computed on multiple sub-graphs, we design a SubG algorithm to compute the probabilistic transition matrix. Furthermore, we propose an efficient dynamic programming algorithm to degrade the time complexity from exponential to polynomial. We give the corresponding theoretical justification and extend the proposed algorithm to incremental dynamic programming algorithm, which further improves the efficiency and can be applied to dynamic graphs. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective. [ABSTRACT FROM AUTHOR]

Abstract: In recent years, various graph-based algorithms have been proposed for semi-supervised learning, where labeled and unlabeled examples are regarded as vertices in a weighted graph, and similarity between examples is encoded by the weight of edges. However, most of these methods cannot be used to deal with dissimilarity or negative similarity. In this paper we propose a mixed label propagation model with a single soft constraint which can effectively handle positive similarity and negative similarity simultaneously, as well as allow the labeled data to be relabeled. Specifically, the soft mixed label propagation model is a fractional quadratic programming problem with a single quadratic constraint, and we apply the global optimal algorithm [1] for solving it, yielding an -global optimal solution in a computational effort of . Numerical comparisons with several existing methods for common test datasets and a class of collaborative filtering problems verify the effectiveness of the method. [Copyright &y& Elsevier]

Highlights: [•] We present the anti-modularity as a quality measure of the anti-community detecting. [•] A label propagation algorithm LPAD for anti-community detection is proposed. [•] The proposed algorithm LPAD does not require the predefined number of anti-communities. [•] The proposed algorithm LPAD has low time complexity of O(n 2). [•] LPAD can maximize the number of edges between clusters and minimize the number of clusters. [ABSTRACT FROM AUTHOR]

Abstract: Analyzing the structure of social networks is of interest in a wide range of disciplines. Unfortunately, sharing social-network datasets is often restrained by privacy considerations. One way to address the privacy concern is to anonymize the data before publishing. Randomly adding or deleting edges from the social graph is one of the anonymization approaches that have been proposed in the literature. Recent studies have quantified the level of anonymity that is obtained by random perturbation by means of a posteriori belief probabilities and, by conducting experiments on small datasets, arrived at the conclusion that random perturbation cannot achieve meaningful levels of anonymity without deteriorating the graph properties. We offer a new information-theoretic perspective on the question of anonymizing a social network by means of random edge additions and deletions. We make an essential distinction between image and preimage anonymity and propose a more accurate quantification, based on entropy, of the anonymity level that is provided by the perturbed network. We explain why the entropy-based quantification, which is global, is more adequate than the previously used local quantification that was based on a posteriori belief probabilities. We also prove that the anonymity level as quantified by means of entropy is always greater than or equal to the one based on a posteriori belief probabilities. In addition, we introduce and explore the method of random sparsification, which randomly removes edges, without adding new ones. Extensive experimentation on several very large datasets shows that randomization techniques for identity obfuscation are back in the game, as they may achieve meaningful levels of anonymity while still preserving properties of the original graph. As the methods we study add and remove edges, it is natural to ask whether an adversary might use the disclosed perturbed graph structure to reconstruct, even partially, the original graph. We thus study the resilience of obfuscation by random sparsification to adversarial attacks that are based on link prediction. Given a general link prediction method, with a predefined level of prediction accuracy, we show how to quantify the level of anonymity that is guaranteed by the obfuscation. We empirically prove that even for very accurate link prediction methods, the level of anonymity guaranteed remains very close to the one before the attack. Finally, we show how the randomization method may be applied in a distributed setting, where the network data is distributed among several non-trusting sites, and explain why randomization is far more suitable for such settings than other existing approaches. [Copyright &y& Elsevier]

Abstract: A Hamiltonian graph G is panpositionably Hamiltonian if for any two distinct vertices x and y of G, it contains a Hamiltonian cycle C such that d C (x, y)= l for any integer l satisfying d G (x, y)⩽ l ⩽⌈∣V(G)∣/2⌉, where d G (x, y) (respectively, d C (x, y)) denotes the distance between vertices x and y in G (respectively, on C), and ∣V(G)∣ is the total number of vertices in G. As the importance of Hamiltonian properties for data communication between units in parallel and distributed systems, the panpositionable Hamiltonicity involves more flexible cycle embedding for message transmission. This paper shows that for two arbitrary nodes x and y of the n-dimensional locally twisted cube LTQ n , n ⩾4, and for any integer l ∈{d}∪{d +2, d +3, d +4, …, 2 n−1}, where , there exists a Hamiltonian cycle C of LTQ n such that d C (x, y)= l. [Copyright &y& Elsevier]

Abstract: Rough sets provide an efficient tool for attribute reduction and rule extraction. However, many important problems in rough set theory, including attribute reduction, are NP-hard and therefore the algorithms for solving them are usually greedy. As a generalization of linear independence in vector spaces, matroids have wide applications in diverse fields, particularly in greedy algorithm design. In this paper, we propose an integration of rough sets and matroids to exploit the advantages of both theories. Specifically, we present definitions of lower and upper rough matroids based on relations from the viewpoint of approximation operators. It is interesting that lower rough matroids based on partial orders coincide with poset matroids, which are a well-known generalization of matroids. A matroid is represented by the lower rough matroid based on both a partial order and an equivalence relation. Lower and upper rough matroids based on equivalence relations coincide with each other. Finally, we present some special types of examples of rough matroids from the viewpoints of approximations and graphs. These interesting results demonstrate the potential for the combination between rough sets and matroids. [Copyright &y& Elsevier]

Abstract: With the increasing amount of information on the Web and the proliferation of RSS offerings, efficient graph-based metadata filtering algorithm for large scale information dissemination is very important today. Matching graph-based documents is expensive due to the expressiveness of the language. The centralized architecture does not work well for the large scale information dissemination service. To address these problems, in this paper we develop a cluster-based publish/subscribe system for filtering graph-based RSS documents. Essentially, we develop two indexing algorithms to enable workload distribution and cluster-based filtering. Furthermore, we proposed an optimized graph matching algorithm which speeds up the constraint evaluation for subscriptions. The experimental results show that we can support one million subscriptions on a compute cluster with 5–20 nodes and the throughput scales linearly with the number of cluster nodes. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a new coloring technique of the edges of the complete graph on 16 vertices, K 16, with three different colors, without producing any monochromatic triangle. This method is totally different from those proposed by [R.E. Greenwood, A.M. Gleason, Combinatorial relations and chromatic graphs, Canadian Journal of Mathematics 7 (1955) 1–7; J.G. Kalbfleish, R.G. Stanton, On the maximal triangle-free edge-chromatic graphs in three colors, Journal of Combinatorial Theory 5 (1968) 9–20; C. Laywine, L.P. Mayberry, A simple construction giving the two non-isomorphic triangle free 3-colored K 16’s, Journal of Combinatorial Theory Series B (1988) 120–124; B. Benhamou, Étude des Symétries et de la Cardinalité en Calcul Propoaitionel: Application aux Algorithmes Syntaxiques, Ph.D. Thesis, University of Aix-Marseilles I, France, 1993] which prove that the classical multicolor Ramsey number R(3,3,3) is 17. This number is the only non-trivial tricolor Ramsey number known till now in spite of more than fifty years of extensive research on Ramsey numbers [S.P. Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics DS1.Revision 11 (2006) 1–60]. We show also how we can convert the Ramsey-graph 3-coloring problem into a satisfiability instance having 2160 clauses of 3-literals each and 360 variables (i.e., a 3-SAT instance). [Copyright &y& Elsevier]