Search

Community search is a fundamental problem in graph analysis. In many applications, network nodes have specific properties that are essential for making sense of communities. In these networks, attributes are associated with nodes to capture their properties. The community influence is a key property of the community that can be employed to sort the communities in a network based on the relevance/importance of certain attributes. Unfortunately, most of the previously introduced community search algorithms over attributed networks neglected the community influence. In this paper, we study the influential attributed community search problem. Different factors for measuring the influence are discussed. Also, different Influential Attributed Community (InfACom) algorithms based on the concept of k-clique are proposed. Two techniques are presented one for sequential implementation with three variations and one for parallel implementation. In addition, we propose efficient algorithms for maintaining the proposed algorithms on dynamic graphs. The proposed algorithms are evaluated on different real datasets. The experimental results show that the summarization technique reduces the size of the graph by approximately half. In addition, it shows that the proposed algorithms $EnhancedExact$ and $Approximate$ outperform the state-of-the-art approaches Incremental Time efficient $(Inc-T)$ , Incremental Space efficient $(Inc-S)$ , $Exact$ , and 2-Approximation $(AppInc)$ in both efficiency and effectiveness. For the $EnhancedExact$ algorithm, the results show that the efficiency is at least 7 times faster than the $Inc-S$ algorithm, at least 4.5 times faster than the $Inc-T$ algorithm, and 2 times faster than the $AppInc$ algorithm. For the $Approximate$ algorithm, the results show that its efficiency is at least 10 times faster than the $Inc-S$ algorithm, at least 6.4 times faster than the $Inc-T$ algorithm, and 3 times faster than the $AppInc$ algorithm. Finally, the results show that the proposed algorithms retrieve cohesive communities with a smaller diameter than all the state-of-the-art approaches.

Graph datasets are common in many application domains and for which their graphs are usually massive. One solution to process such massive graphs is summarization. There are two kinds of graphs, stationary and stream. For stationary graphs, a number of summarization algorithms are available while for graph stream there is no a comprehensive summarization method that summarizes a graph stream based on the structure, vertex attributes or both with varying contributions. This is because of challenges of graph stream, which are volume of data and changing of data over time. In this paper, we propose a method based on sliding-window model for which summarizes a graph stream based on a combination of the structure and vertex attributes. We proposed a new structure for summary graphs and also proposed new methods for comparing two summary graphs. To the best of our knowledge, this is the first method that summarizes a graph stream based on both the structure and vertex attributes with varying contributions. Through extensive experiments on real dataset of Amazon co-purchasing products, we have demonstrated the performance of the proposed method.

International audience; In asynchronous Boolean models, periodic solutions are represented by terminal strongly connected graphs, which are typically composed of hundreds of states and transitions. For biological systems, it becomes a challenging task to compare such mathematical objects with biological knowledge, or interpret the transitions inside an attractor in terms of the sequence of events in a biological cycle. A recent methodology generates summary graphs to help visualizing complex asynchronous attractors and order the dynamic progression based on known biological data. In this article we apply this method to a Boolean model of the mammalian circadian clock, for which the summary graph recovers the main phases of the cycle, in the expected order. It also provides a detailed view of the attractor, suggesting improvements in the design of the model's logical rules and highlighting groups of transitions that are essential for the attractor's robustness.

In this paper, we present a system called QueSTS, which generates a query specific extractive summary of a selected set of documents. We have proposed an integrated graph approach to represent the contextual relationships among sentences of all the input documents. These relationships are exploited and several sub-graphs of the integrated graph are constructed. These sub-graphs consist of sentences that are highly relevant to the query and that are highly related to each other. These sub-graphs are ranked by a scoring model. The highest ranked sub-graph which is rich in query relevant information is selected as a query specific summary. A sentence ordering strategy has also been proposed by us to improve the coherence of the summary. Sentences in the selected summary are sequenced as per the above strategy. Experimental results show that the summaries generated by the QueSTS system are significantly better than other systems in terms of user satisfaction. � 2010 World Scientific Publishing Company.

In this paper, we study classes of graphs with three types of edges that capture the modified independence structure of a directed acyclic graph (DAG) after marginalisation over unobserved variables and conditioning on selection variables using the $m$-separation criterion. These include MC, summary, and ancestral graphs. As a modification of MC graphs, we define the class of ribbonless graphs (RGs) that permits the use of the $m$-separation criterion. RGs contain summary and ancestral graphs as subclasses, and each RG can be generated by a DAG after marginalisation and conditioning. We derive simple algorithms to generate RGs, from given DAGs or RGs, and also to generate summary and ancestral graphs in a simple way by further extension of the RG-generating algorithm. This enables us to develop a parallel theory on these three classes and to study the relationships between them as well as the use of each class., Comment: Published in at http://dx.doi.org/10.3150/12-BEJ454 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

As there are also graph methods of circuit analysis in addition to algebraic methods, it is, in theory, clearly possible to carry out an analysis of a whole switched circuit in two-phase switching exclusively by the graph method as well. This article deals with two methods of full-graph solving of switched circuits: by transformation graphs and by two-graphs. It deals with the circuit switched capacitors and the switched current, too. All methods are presented in an equally detailed steps to be able to compare., {"references":["D. Biolek, Solving Electronics Circuits. Praque, BEN Publisher 2004.","T. Dostál, The Analysis of the Active Components Containing Switched\nCapacitors by Nodal Voltage Method. Electronics horizont, Vol. 45,\nNo.I, 1984, pp. 21-26..","P. Martinek, P. Boreš, J. Hospodka, Electrics Filters. CVUT Publisher\nPraque, 2003.","Toumazou, Ch., Circuits and Systems Tutorials. IEEE Press Inc., New\nYork, 1996.","J. Vlach, K. Singhal, Computer Methods for Circuit Analysis and\nDesign. Van Nostrand Reynhold New York, 1994."]}

This paper introduces a class of graphical independence models that is closed under marginalization and conditioning but that contains all DAG independence models. This class of graphs, called maximal ancestral graphs, has two attractive features: there is at most one edge between each pair of vertices; every missing edge corresponds to an independence relation. These features lead to a simple parameterization of the corresponding set of distributions in the Gaussian case.