Journal articles: 'Overlapping graphs'

1

HARALAMBIDES, JAMES, and SPYROS TRAGOUDAS. "BIPARTITIONING INTO OVERLAPPING SETS." International Journal of Foundations of Computer Science 06, no. 01 (March 1995): 67–88. http://dx.doi.org/10.1142/s0129054195000068.

Full text

Abstract:

We consider a generalization of the min-cut partitioning problem where we partition a graph G=(V,E) into two sets V1 and V2 such that |V1∩V2|≤d, d<|V|, and such that |{(u, v)|u∈V1−V2, v∈V2−V1}| is minimized. The problem is trivially solvable using flow techniques for any fixed d, but we show that it is NP-hard for integer values of d. It remains NP-hard if we impose restrictions on the size of V1, i.e., |V1|=k, k∈Z+. The latter problem variation may apply in VLSI layout and hypertext partitioning. We present polynomial time algorithms for the special cases of solid grids and series-parallel graphs. Series-parallel graphs find applications in hypertext partitioning whereas grid graphs model the mapping of a class of Partial Differential Equation computations into parallel machines.

APA, Harvard, Vancouver, ISO, and other styles

2

Bhagavathi, D., H. Gurla, S. Olariu, J. L. Schwing, and J. Zhang. "Time- and Cost-Optimal Parallel Algorithms for the Dominance and Visibility Graphs." VLSI Design 4, no. 1 (January 1, 1996): 33–40. http://dx.doi.org/10.1155/1996/40175.

Full text

Abstract:

The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in θ(log n) time using n processors in the CREW model.

APA, Harvard, Vancouver, ISO, and other styles

3

Evans, T. S. "Clique graphs and overlapping communities." Journal of Statistical Mechanics: Theory and Experiment 2010, no. 12 (December 23, 2010): P12037. http://dx.doi.org/10.1088/1742-5468/2010/12/p12037.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Galbrun, Esther, Aristides Gionis, and Nikolaj Tatti. "Overlapping community detection in labeled graphs." Data Mining and Knowledge Discovery 28, no. 5-6 (August 2, 2014): 1586–610. http://dx.doi.org/10.1007/s10618-014-0373-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

CRAMPES, MICHEL, and MICHEL PLANTIÉ. "A UNIFIED COMMUNITY DETECTION, VISUALIZATION AND ANALYSIS METHOD." Advances in Complex Systems 17, no. 01 (February 2014): 1450001. http://dx.doi.org/10.1142/s0219525914500015.

Full text

Abstract:

With the widespread social networks on the Internet, community detection in social graphs has recently become an important research domain. Interest was initially limited to unipartite graph inputs and partitioned community outputs. More recently, bipartite graphs, directed graphs and overlapping communities have all been investigated. Few contributions however have encompassed all three types of graphs simultaneously. In this paper, we present a method that unifies community detection for these three types of graphs while at the same time it merges partitioned and overlapping communities. Moreover, the results are visualized in a way that allows for analysis and semantic interpretation. For validation purposes this method is experimented on some well-known simple benchmarks and then applied to real data: photos and tags in Facebook and Human Brain Tractography data. This last application leads to the possibility of applying community detection methods to other fields such as data analysis with original enhanced performances.

APA, Harvard, Vancouver, ISO, and other styles

6

Miro, Eden Delight, Aliw-iw Zambrano, and Agnes Garciano. "Construction of weavings in the plane." Acta Crystallographica Section A Foundations and Advances 74, no. 1 (January 1, 2018): 25–35. http://dx.doi.org/10.1107/s205327331701422x.

Full text

Abstract:

This work develops, in graph-theoretic terms, a methodology for systematically constructing weavings of overlapping nets derived from 2-colorings of the plane. From a 2-coloring, two disjoint simple, connected graphs called nets are constructed. The union of these nets forms an overlapping net, and a weaving map is defined on the intersection points of the overlapping net to form a weaving. Furthermore, a procedure is given for the construction of mixed overlapping nets and for deriving weavings from them.

APA, Harvard, Vancouver, ISO, and other styles

7

Wang, Guishen, Yuanwei Wang, Kaitai Wang, Zhihua Liu, Lijuan Zhang, Yu Zhou, and Qinan Yao. "An overlapping community detection algorithm based on node distance of line graph." Modern Physics Letters B 33, no. 26 (September 20, 2019): 1950322. http://dx.doi.org/10.1142/s0217984919503226.

Full text

Abstract:

Overlapping community detection is a hot topic in research of complex networks. Link community detection is a popular approach to discover overlapping communities. Line graph is a widely used model in link community detection. In this paper, we propose an overlapping community detection algorithm based on node distance of line graph. Considering topological structure of links in graphs, we use line graph to transform links of graph into nodes of line graph. Then, we calculate node distance of line graph according to their dissimilarity. After getting distance matrix, we proposed a new [Formula: see text] measure based on nodes of line graph and combine it with clustering algorithm by fast search and density peak to identify node communities of line graph. Finally, we acquire overlapping node communities after transforming node communities of line graph back to graph. The experimental results show that our algorithm achieves a higher performance on normalized mutual information metric.

APA, Harvard, Vancouver, ISO, and other styles

8

Yoshida, Tetsuya. "Weighted line graphs for overlapping community discovery." Social Network Analysis and Mining 3, no. 4 (March 21, 2013): 1001–13. http://dx.doi.org/10.1007/s13278-013-0104-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Zhang, Zhenkun, and Hongjian Lai. "On Critical Unicyclic Graphs with Cutwidth Four." AppliedMath 2, no. 4 (November 17, 2022): 621–37. http://dx.doi.org/10.3390/appliedmath2040036.

Full text

Abstract:

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line Pn with n=|V(G)| vertices in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with a cutwidth of k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, we first verified some structural properties of k-cutwidth critical unicyclic graphs with k>1. We then mainly investigated the critical unicyclic graph set T with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs.

APA, Harvard, Vancouver, ISO, and other styles

10

Singh, Sakshi. "Algorithm and Techniques for Overlapping Community Detection." International Journal of Advance Research and Innovation 2, no. 2 (2014): 52–60. http://dx.doi.org/10.51976/ijari.221408.

Full text

Abstract:

A lot of phenomenon, real world and otherwise can be conveniently represented as graphs, with the nodes corresponding to the entities and the edges representing the interaction be- tween those entities. Communities or modules, which are groups of nodes densely connected to each other within the community but sparsely linked to other communities and the rest of the graph, often having similar structural and functional properties. A lot of algorithms have been proposed to partition the set of vertices into communities; such a partition exclusively puts a node into one community or the other. But in real life a node can belong to multiple communities simultaneously, i.e. the communities can overlap. Different metrics have been proposed. We reduce the modularity maximization problem for splitting the graph into two communities to the MAX-CUT problem with both positive and negative weights. We introduce and analyze three approximation algorithms to maximize modularity for the two community case; recursive bi-partitioning can be carried out as long as modularity increases to split into more than two communities.

APA, Harvard, Vancouver, ISO, and other styles

11

Evans, T. S., and R. Lambiotte. "Line graphs of weighted networks for overlapping communities." European Physical Journal B 77, no. 2 (September 2010): 265–72. http://dx.doi.org/10.1140/epjb/e2010-00261-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

KUKLUK, JACEK P., LAWRENCE B. HOLDER, and DIANE J. COOK. "INFERENCE OF EDGE REPLACEMENT GRAPH GRAMMARS." International Journal on Artificial Intelligence Tools 17, no. 03 (June 2008): 539–54. http://dx.doi.org/10.1142/s0218213008004047.

Full text

Abstract:

We describe an algorithm and experiments for inference of edge replacement graph grammars. This method generates candidate recursive graph grammar productions based on isomorphic subgraphs which overlap by two nodes. If there is no edge between the two overlapping nodes, the method generates a recursive graph grammar production with a virtual edge. We guide the search for the graph grammar based on the size of the grammar and the portion of the graph described by the grammar. We show experiments where we generate graphs from known graph grammars, use our method to infer the grammar from the generated graphs, and then measure the error between the original and inferred grammars. Experiments show that the method performs well on several types of grammars, and specifically that error decreases with increased numbers of unique labels in the graph.

APA, Harvard, Vancouver, ISO, and other styles

13

Gupta, Sumit, and Dhirendra Pratap Singh. "Recent trends on community detection algorithms: A survey." Modern Physics Letters B 34, no. 35 (September 17, 2020): 2050408. http://dx.doi.org/10.1142/s0217984920504084.

Full text

Abstract:

In today’s world scenario, many of the real-life problems and application data can be represented with the help of the graphs. Nowadays technology grows day by day at a very fast rate; applications generate a vast amount of valuable data, due to which the size of their representation graphs is increased. How to get meaningful information from these data become a hot research topic. Methodical algorithms are required to extract useful information from these raw data. These unstructured graphs are not scattered in nature, but these show some relationships between their basic entities. Identifying communities based on these relationships improves the understanding of the applications represented by graphs. Community detection algorithms are one of the solutions which divide the graph into small size clusters where nodes are densely connected within the cluster and sparsely connected across. During the last decade, there are lots of algorithms proposed which can be categorized into mainly two broad categories; non-overlapping and overlapping community detection algorithm. The goal of this paper is to offer a comparative analysis of the various community detection algorithms. We bring together all the state of art community detection algorithms related to these two classes into a single article with their accessible benchmark data sets. Finally, we represent a comparison of these algorithms concerning two parameters: one is time efficiency, and the other is how accurately the communities are detected.

APA, Harvard, Vancouver, ISO, and other styles

14

Drobyshevskiy, M., A. Korshunov, and D. Turdakov. "Parallel modularity computation for directed weighted graphs with overlapping communities." Proceedings of the Institute for System Programming of the RAS 28, no. 6 (2016): 153–70. http://dx.doi.org/10.15514/ispras-2016-28(6)-11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Gui, Chun, Ruisheng Zhang, Rongjing Hu, Guoming Huang, and Jiaxuan Wei. "Overlapping communities detection based on spectral analysis of line graphs." Physica A: Statistical Mechanics and its Applications 498 (May 2018): 50–65. http://dx.doi.org/10.1016/j.physa.2018.01.025.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Lamy, Jean-Baptiste. "Visualizing undirected graphs and symmetric square matrices as overlapping sets." Multimedia Tools and Applications 78, no. 23 (May 11, 2019): 33091–112. http://dx.doi.org/10.1007/s11042-019-7655-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

van der Hofstad, Remco, Júlia Komjáthy, and Viktória Vadon. "Random intersection graphs with communities." Advances in Applied Probability 53, no. 4 (November 22, 2021): 1061–89. http://dx.doi.org/10.1017/apr.2021.12.

Full text

Abstract:

AbstractRandom intersection graphs model networks with communities, assuming an underlying bipartite structure of communities and individuals, where these communities may overlap. We generalize the model, allowing for arbitrary community structures within the communities. In our new model, communities may overlap, and they have their own internal structure described by arbitrary finite community graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, show local weak convergence (including convergence of subgraph counts), and derive the asymptotic degree distribution and the local clustering coefficient.

APA, Harvard, Vancouver, ISO, and other styles

18

Huang, Mingqing, Qingshan Jiang, Qiang Qu, and Abdur Rasool. "An Overlapping Community Detection Approach in Ego-Splitting Networks Using Symmetric Nonnegative Matrix Factorization." Symmetry 13, no. 5 (May 13, 2021): 869. http://dx.doi.org/10.3390/sym13050869.

Full text

Abstract:

Overlapping clustering is a fundamental and widely studied subject that identifies all densely connected groups of vertices and separates them from other vertices in complex networks. However, most conventional algorithms extract modules directly from the whole large-scale graph using various heuristics, resulting in either high time consumption or low accuracy. To address this issue, we develop an overlapping community detection approach in Ego-Splitting networks using symmetric Nonnegative Matrix Factorization (ESNMF). It primarily divides the whole network into many sub-graphs under the premise of preserving the clustering property, then extracts the well-connected sub-sub-graph round each community seed as prior information to supplement symmetric adjacent matrix, and finally identifies precise communities via nonnegative matrix factorization in each sub-network. Experiments on both synthetic and real-world networks of publicly available datasets demonstrate that the proposed approach outperforms the state-of-the-art methods for community detection in large-scale networks.

APA, Harvard, Vancouver, ISO, and other styles

19

Cyvin, S. J., J. Brunvoll, B. N. Cyvin, and W. Lüttke. "Enumeration of the Staggered Conformers of Alkanes." Zeitschrift für Naturforschung A 50, no. 9 (September 1, 1995): 857–63. http://dx.doi.org/10.1515/zna-1995-0911.

Full text

Abstract:

Abstract Alkanoid systems are chemical graphs which can be embedded in the diamond lattice. They correspond to the staggered conformers of alkanes. Non-overlapping and overlapping systems are defined. The previously deduced algebraic solution for the numbers of unbranched alkanoids is revisited and reformulated in terms of generating functions. Computerized enumerations for non-overlapping alkanoids, both unbranched and branched, are reported. Some of the smallest overlap ping unbranched alkanoids are generated by a method called combinatorial constructions.

APA, Harvard, Vancouver, ISO, and other styles

20

Wu, Jun, and Minghao Yin. "Local Search for Diversified Top-k s-plex Search Problem (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 18 (May 18, 2021): 15929–30. http://dx.doi.org/10.1609/aaai.v35i18.17961.

Full text

Abstract:

The diversified top-k s-plex (DTKSP) search problem aims to find k maximal s-plexes that cover the maximum number of vertices with lower overlapping in a given graph. In this paper, we first formalize the diversified top-k s-plex search problem and prove the NP-hardness of it. Second, we proposed a local search algorithm for solving the diversified top-k s-plex search problem based on some novel ideas. Experiments on real-world massive graphs show the effectiveness of our algorithm.

APA, Harvard, Vancouver, ISO, and other styles

21

Nicosia, V., G. Mangioni, V. Carchiolo, and M. Malgeri. "Extending the definition of modularity to directed graphs with overlapping communities." Journal of Statistical Mechanics: Theory and Experiment 2009, no. 03 (March 16, 2009): P03024. http://dx.doi.org/10.1088/1742-5468/2009/03/p03024.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Todeschini, Adrien, Xenia Miscouridou, and François Caron. "Exchangeable random measures for sparse and modular graphs with overlapping communities." Journal of the Royal Statistical Society: Series B (Statistical Methodology) 82, no. 2 (March 9, 2020): 487–520. http://dx.doi.org/10.1111/rssb.12363.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Bhatia, Vandana, and Rinkle Rani. "A distributed overlapping community detection model for large graphs using autoencoder." Future Generation Computer Systems 94 (May 2019): 16–26. http://dx.doi.org/10.1016/j.future.2018.10.045.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Kejriwal, Mayank. "Knowledge Graphs: A Practical Review of the Research Landscape." Information 13, no. 4 (March 23, 2022): 161. http://dx.doi.org/10.3390/info13040161.

Full text

Abstract:

Knowledge graphs (KGs) have rapidly emerged as an important area in AI over the last ten years. Building on a storied tradition of graphs in the AI community, a KG may be simply defined as a directed, labeled, multi-relational graph with some form of semantics. In part, this has been fueled by increased publication of structured datasets on the Web, and well-publicized successes of large-scale projects such as the Google Knowledge Graph and the Amazon Product Graph. However, another factor that is less discussed, but which has been equally instrumental in the success of KGs, is the cross-disciplinary nature of academic KG research. Arguably, because of the diversity of this research, a synthesis of how different KG research strands all tie together could serve a useful role in enabling more ‘moonshot’ research and large-scale collaborations. This review of the KG research landscape attempts to provide such a synthesis by first showing what the major strands of research are, and how those strands map to different communities, such as Natural Language Processing, Databases and Semantic Web. A unified framework is suggested in which to view the distinct, but overlapping, foci of KG research within these communities.

APA, Harvard, Vancouver, ISO, and other styles

25

Su, Jing, Hui Sun, and Bing Yao. "Odd-Graceful Total Colorings for Constructing Graphic Lattice." Mathematics 10, no. 1 (December 30, 2021): 109. http://dx.doi.org/10.3390/math10010109.

Full text

Abstract:

The security of passwords generated by the graphic lattices is based on the difficulty of the graph isomorphism, graceful tree conjecture, and total coloring conjecture. A graphic lattice is generated by a graphic base and graphical operations, where a graphic base is a group of disjointed, connected graphs holding linearly independent properties. We study the existence of graphic bases with odd-graceful total colorings and show graphic lattices by vertex-overlapping and edge-joining operations; we prove that these graphic lattices are closed to the odd-graceful total coloring.

APA, Harvard, Vancouver, ISO, and other styles

26

Manimaran, P., and K. Duraiswamy. "Identifying Overlying Group of People through Clustering." International Journal of Information Technology and Web Engineering 7, no. 4 (October 2012): 50–60. http://dx.doi.org/10.4018/jitwe.2012100104.

Full text

Abstract:

Folksonomies like Delicious and LastFm are modeled as multilateral (user-resource-tag) hypergraphs for studying their network properties. Detecting communities of similar nodes from such networks is a challenging problem. Most existing algorithms for community detection in folksonomies assign unique communities to nodes, whereas in reality, users have multiple relevant interests and same resource is often tagged with semantically different tags. Few attempts to perceive overlapping communities work on forecasts of hypergraph, which results in momentous loss of information contained in original tripartite structure. Propose first algorithm to detect overlapping communities in folksonomies using complete hypergraph structure. The authors’ algorithm converts a hypergraph into its parallel line graph, using measures of hyperedge similarity, whereby any community detection algorithm on unipartite graphs can be used to produce intersecting communities in folksonomy. Through extensive experiments on synthetic as well as real folksonomy data, demonstrate that proposed algorithm can detect better community structures as compared to existing state-of-the-art algorithms for folksonomies.

APA, Harvard, Vancouver, ISO, and other styles

27

Abdollahyan, Maryam, Greg Elgar, and Fabrizio Smeraldi. "Identifying Potential Regulatory Elements by Transcription Factor Binding Site Alignment Using Partial Order Graphs." International Journal of Foundations of Computer Science 29, no. 08 (December 2018): 1345–54. http://dx.doi.org/10.1142/s0129054118430074.

Full text

Abstract:

Identification and functional characterization of regulatory elements in the human genome is a challenging task. A sequence feature commonly used to predict regulatory activity is the co-occurrence of transcription factor binding sites (TFBSs) in regulatory regions. In this work, we present a graph-based approach to detect frequently co-occurring TFBSs in evolutionarily conserved non-coding elements (CNEs). We introduce a graph representation of the sequence of TFBSs identified in a CNE that allows us to handle overlapping binding sites. We use a dynamic programming algorithm to align such graphs and determine the relative enrichment of short sequences of TFBSs in the alignments. We evaluate our approach on a set of functionally validated CNEs. Our findings include a regulatory signature composed of co-occurring Pbx-Hox and Meis binding motifs associated with hindbrain enhancer activity.

APA, Harvard, Vancouver, ISO, and other styles

28

MONGIOVÌ, MISAEL, RAFFAELE DI NATALE, ROSALBA GIUGNO, ALFREDO PULVIRENTI, ALFREDO FERRO, and RODED SHARAN. "SIGMA: A SET-COVER-BASED INEXACT GRAPH MATCHING ALGORITHM." Journal of Bioinformatics and Computational Biology 08, no. 02 (April 2010): 199–218. http://dx.doi.org/10.1142/s021972001000477x.

Full text

Abstract:

Network querying is a growing domain with vast applications ranging from screening compounds against a database of known molecules to matching sub-networks across species. Graph indexing is a powerful method for searching a large database of graphs. Most graph indexing methods to date tackle the exact matching (isomorphism) problem, limiting their applicability to specific instances in which such matches exist. Here we provide a novel graph indexing method to cope with the more general, inexact matching problem. Our method, SIGMA, builds on approximating a variant of the set-cover problem that concerns overlapping multi-sets. We extensively test our method and compare it to a baseline method and to the state-of-the-art Grafil. We show that SIGMA outperforms both, providing higher pruning power in all the tested scenarios.

APA, Harvard, Vancouver, ISO, and other styles

29

Olifer, Dmitrij, Nikolaj Goranin, Antanas Cenys, Arnas Kaceniauskas, and Justinas Janulevicius. "Defining the Minimum Security Baseline in a Multiple Security Standards Environment by Graph Theory Techniques." Applied Sciences 9, no. 4 (February 17, 2019): 681. http://dx.doi.org/10.3390/app9040681.

Full text

Abstract:

One of the best ways to protect an organization’s assets is to implement security requirements defined by different standards or best practices. However, such an approach is complicated and requires specific skills and knowledge. In case an organization applies multiple security standards, several problems can arise related to overlapping or conflicting security requirements, increased expenses on security requirement implementation, and convenience of security requirement monitoring. To solve these issues, we propose using graph theory techniques. Graphs allow the presentation of security requirements of a standard as graph vertexes and edges between vertexes, and would show the relations between different requirements. A vertex cover algorithm is proposed for minimum security requirement identification, while graph isomorphism is proposed for comparing existing organization controls against a set of minimum requirements identified in the previous step.

APA, Harvard, Vancouver, ISO, and other styles

30

Altaf-Ul-Amin, Md, Masayoshi Wada, and Shigehiko Kanaya. "Partitioning a PPI Network into Overlapping Modules Constrained by High-Density and Periphery Tracking." ISRN Biomathematics 2012 (May 23, 2012): 1–11. http://dx.doi.org/10.5402/2012/726429.

Full text

Abstract:

This paper presents an algorithm called DPClusO for partitioning simple graphs into overlapping modules, that is, clusters constrained by density and periphery tracking. The major advantages of DPClusO over the related and previously published algorithm DPClus are shorter running time and ensuring coverage, that is, each node goes to at least one module. DPClusO is a general-purpose clustering algorithm and useful for finding overlapping cohesive groups in a simple graph for any type of application. This work shows that the modules generated by DPClusO from several PPI networks of yeast with high-density constraint match with more known complexes compared to some other recently published complex generating algorithms. Furthermore, the biological significance of the high density modules has been demonstrated by comparing their P values in the context of Gene Ontology (GO) terms with those of the randomly generated modules having the same size, distribution, and zero density. As a consequence, it was also learnt that a PPI network is a combination of mainly high-density and star-like modules.

APA, Harvard, Vancouver, ISO, and other styles

31

Wu, Jun, and Minghao Yin. "A Hybrid Evolutionary Algorithm for the Diversified Top-k Weight Clique Search Problem (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 11 (June 28, 2022): 13083–84. http://dx.doi.org/10.1609/aaai.v36i11.21678.

Full text

Abstract:

The diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique search problem, which extends the DTKC search problem by taking into account the weight of vertices. This problem involves finding at most k maximal weighted cliques that cover maximum weight of vertices with low overlapping in a given graph. In this study, a mixed integer linear program constraint formulation is proposed to model DTKWC search problem and an efficient hybrid evolutionary algorithm (HEA-D) based on some heuristic strategies is proposed to tackle it. Experiments on two sets of 110 graphs show that HEA-D outperforms the state-of-art methods.

APA, Harvard, Vancouver, ISO, and other styles

32

Chen, Yifan, Xiang Zhao, Chuan Xiao, Weiming Zhang, and Jiuyang Tang. "Efficient and Scalable Graph Similarity Joins in MapReduce." Scientific World Journal 2014 (2014): 1–11. http://dx.doi.org/10.1155/2014/749028.

Full text

Abstract:

Along with the emergence of massive graph-modeled data, it is of great importance to investigate graph similarity joins due to their wide applications for multiple purposes, including data cleaning, and near duplicate detection. This paper considers graph similarity joins with edit distance constraints, which return pairs of graphs such that their edit distances are no larger than a given threshold. Leveraging the MapReduce programming model, we proposeMGSJoin, a scalable algorithm following the filtering-verification framework for efficient graph similarity joins. It relies on counting overlapping graph signatures for filtering out nonpromising candidates. With the potential issue of too many key-value pairs in the filtering phase, spectral Bloom filters are introduced to reduce the number of key-value pairs. Furthermore, we integrate the multiway join strategy to boost the verification, where a MapReduce-based method is proposed for GED calculation. The superior efficiency and scalability of the proposed algorithms are demonstrated by extensive experimental results.

APA, Harvard, Vancouver, ISO, and other styles

33

Nawalaniec, Wojciech, Katarzyna Necka, and Vladimir Mityushev. "Effective Conductivity of Densely Packed Disks and Energy of Graphs." Mathematics 8, no. 12 (December 4, 2020): 2161. http://dx.doi.org/10.3390/math8122161.

Full text

Abstract:

The theory of structural approximations is extended to two-dimensional double periodic structures and applied to determination of the effective conductivity of densely packed disks. Statistical simulations of non-overlapping disks with the different degrees of clusterization are considered. The obtained results shows that the distribution of inclusions in a composite, as an amount of geometrical information, remains in the discrete corresponding Voronoi tessellation, hence, precisely determines the effective conductivity for random composites.

APA, Harvard, Vancouver, ISO, and other styles

34

Yan, Yongjie, Guang Yu, Xiangbin Yan, and Hui Xie. "Community cores expansion for overlapping community detection in complex networks." Modern Physics Letters B 32, no. 33 (November 30, 2018): 1850405. http://dx.doi.org/10.1142/s0217984918504055.

Full text

Abstract:

The identification of communities has attracted considerable attentions in the last few years. We propose a novel heuristic algorithm for overlapping community detection based on community cores in complex networks. We introduce a novel clique percolation algorithm and maximize cliques in the finding overlapping communities (node covers) in graphs. We show how vertices can be used to quantify types of local structure presented in a community and identify group nodes that have similar roles in relation to their neighbors. We compare the approach with other three common algorithms in the analysis of the Zachary’s karate club network and the dolphins network. Experimental results in real-world and synthetic datasets (Lancichinetti–Fortunato–Radicchi (LFR) benchmark networks [A. Lancichinetti and S. Fortunato, Phys. Rev. E 80 (2009) 016118]) demonstrate the model has scalability and is well behaved.

APA, Harvard, Vancouver, ISO, and other styles

35

Chang, Furong, Bofeng Zhang, Yue Zhao, Songxian Wu, and Kenji Yoshigoe. "Overlapping Community Detecting Based on Complete Bipartite Graphs in Micro-Bipartite Network Bi-Egonet." IEEE Access 7 (2019): 91488–98. http://dx.doi.org/10.1109/access.2019.2926987.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Dimitrakopoulos, Christos, Konstantinos Theofilatos, Andreas Pegkas, Spiros Likothanassis, and Seferina Mavroudi. "Predicting overlapping protein complexes from weighted protein interaction graphs by gradually expanding dense neighborhoods." Artificial Intelligence in Medicine 71 (July 2016): 62–69. http://dx.doi.org/10.1016/j.artmed.2016.05.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Wei, Yifang, Lisa Singh, David Buttler, and Brian Gallagher. "Using semantic graphs to detect overlapping target events and story lines from newspaper articles." International Journal of Data Science and Analytics 5, no. 1 (November 27, 2017): 41–60. http://dx.doi.org/10.1007/s41060-017-0066-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Dumitriu, Ioana, and Elliot Paquette. "Spectra of overlapping Wishart matrices and the Gaussian free field." Random Matrices: Theory and Applications 07, no. 02 (March 20, 2018): 1850003. http://dx.doi.org/10.1142/s201032631850003x.

Full text

Abstract:

Consider a doubly-infinite array of i.i.d. centered variables with moment conditions, from which one can extract a finite number of rectangular, overlapping submatrices, and form the corresponding Wishart matrices. We show that under basic smoothness assumptions, centered linear eigenstatistics of such matrices converge jointly to a Gaussian vector with an interesting covariance structure. This structure, which is similar to those appearing in [A. Borodin, Clt for spectra of submatrices of Wigner random matrices, Mosc. Math. J. 14(1) (2014) 29–38; A. Borodin and V. Gorin, General beta Jacobi corners process and the Gaussian free field, preprint (2013), arXiv:1305.3627; T. Johnson and S. Pal, Cycles and eigenvalues of sequentially growing random regular graphs, Ann. Probab. 42(4) (2014) 1396–1437], can be described in terms of the height function, and leads to a connection with the Gaussian Free Field on the upper half-plane. Finally, we generalize our results from univariate polynomials to a special class of planar functions.

APA, Harvard, Vancouver, ISO, and other styles

39

Belyi, Alexander B., Stanislav L. Sobolevsky, Alexander N. Kurbatski, and Carlo Ratti. "Improved upper bounds in clique partitioning problem." Journal of the Belarusian State University. Mathematics and Informatics, no. 3 (November 29, 2019): 93–104. http://dx.doi.org/10.33581/2520-6508-2019-3-93-104.

Full text

Abstract:

In this work, a problem of partitioning a complete weighted graph into cliques in such a way that sum of edge weights between vertices belonging to the same clique is maximal is considered. This problem is known as a clique partitioning problem. It arises in many applications and is a varian of classical clustering problem. However, since the problem, as well as many other combinatorial optimization problems, is NP-hard, finding its exact solution often appears hard. In this work, a new method for constructing upper bounds of partition quality function values is proposed, and it is shown how to use these upper bounds in branch and bound technique for finding an exact solution. Proposed method is based on the usage of triangles constraining maximal possible quality of partition. Novelty of the method lies in possibility of using triangles overlapping by edges, which allows to find much tighter bounds than when using only non-overlapping subgraphs. Apart from constructing initial estimate, a method of its recalculation, when fixing edges on each step of branch and bound method, is described. Test results of proposed algorithm on generated sets of random graphs are provided. It is shown, that version that uses new bounds works several times faster than previously known methods.

APA, Harvard, Vancouver, ISO, and other styles

40

Yoon, Jisung, Kai-Cheng Yang, Woo-Sung Jung, and Yong-Yeol Ahn. "Persona2vec: a flexible multi-role representations learning framework for graphs." PeerJ Computer Science 7 (March 30, 2021): e439. http://dx.doi.org/10.7717/peerj-cs.439.

Full text

Abstract:

Graph embedding techniques, which learn low-dimensional representations of a graph, are achieving state-of-the-art performance in many graph mining tasks. Most existing embedding algorithms assign a single vector to each node, implicitly assuming that a single representation is enough to capture all characteristics of the node. However, across many domains, it is common to observe pervasively overlapping community structure, where most nodes belong to multiple communities, playing different roles depending on the contexts. Here, we propose persona2vec, a graph embedding framework that efficiently learns multiple representations of nodes based on their structural contexts. Using link prediction-based evaluation, we show that our framework is significantly faster than the existing state-of-the-art model while achieving better performance.

APA, Harvard, Vancouver, ISO, and other styles

41

WANG, Chen, Hamzah ABDUL-RAHMAN, and Wei See CH’NG. "ANT COLONY OPTIMIZATION (ACO) IN SCHEDULING OVERLAPPING ARCHITECTURAL DESIGN ACTIVITIES." JOURNAL OF CIVIL ENGINEERING AND MANAGEMENT 22, no. 6 (June 8, 2016): 780–91. http://dx.doi.org/10.3846/13923730.2014.914100.

Full text

Abstract:

The increasing complexity of architectural design works refers to the need for high quality design solutions for overlapping activities through a shorter time period. Conventional network analysis techniques such as CPM could only represent sequential processes yet it is unable to handle a process which contains iterations so that it leads to the occurrence of unwanted omission of logic or information links between design activities. Ant Colony Optimization emerged as an efficient metaheuristic technique for solving computational problems in finding good paths through graphs. This research aims to develop an ACO based Design Activity Scheduling model (ACO-DAS) for the scheduling of overlapping architectural design activities and to test the workability of ACO-DAS through a hypothetical run. From the computational results of both CPM and ACO methods, the determination of critical path using ACO-DAS model resulted in a design duration at 50 while that for CPM was as long as 78. The durations of architectural design activities have been significantly shortened by ACO-DAS. ACO-DAS results in shorter design completion time thus it deems more advanced than CPM.

APA, Harvard, Vancouver, ISO, and other styles

42

Alasadi, Mustafa K., and Ghusoon Idan Arb. "Community-based framework for influence maximization problem in social networks." Indonesian Journal of Electrical Engineering and Computer Science 24, no. 3 (December 1, 2021): 1604. http://dx.doi.org/10.11591/ijeecs.v24.i3.pp1604-1609.

Full text

Abstract:

<p>Given a social graph, the influence maximization problem (IMP) is the act of selecting a group of nodes that cause maximum influence if they are considered as seed nodes of a diffusion process. IMP is an active research area in social network analysis due to its practical need in applications like viral marketing, target advertisement, and recommendation system. In this work, we propose an efficient solution for IMP based on the social network structure. The community structure is a property of real-world graphs. In fact, communities are often overlapping because of the involvement of users in many groups (family, workplace, and friends). These users are represented by overlapped nodes in the social graphs and they play a special role in the information diffusion process. This fact prompts us to propose a solution framework consisting of three phases: firstly, the community structure is discovered, secondly, the candidate seeds are generated, then lastly the set of final seed nodes are selected. The aim is to maximize the influence with the community diversity of influenced users. The study was validated using synthetic as well as real social network datasets. The experimental results show improvement over baseline methods and some important conclusions were reported.</p>

APA, Harvard, Vancouver, ISO, and other styles

43

Muñoz-Baena, Laura, and Art F. Y. Poon. "Using networks to analyze and visualize the distribution of overlapping genes in virus genomes." PLOS Pathogens 18, no. 2 (February 24, 2022): e1010331. http://dx.doi.org/10.1371/journal.ppat.1010331.

Full text

Abstract:

Gene overlap occurs when two or more genes are encoded by the same nucleotides. This phenomenon is found in all taxonomic domains, but is particularly common in viruses, where it may increase the information content of compact genomes or influence the creation of new genes. Here we report a global comparative study of overlapping open reading frames (OvRFs) of 12,609 virus reference genomes in the NCBI database. We retrieved metadata associated with all annotated open reading frames (ORFs) in each genome record to calculate the number, length, and frameshift of OvRFs. Our results show that while the number of OvRFs increases with genome length, they tend to be shorter in longer genomes. The majority of overlaps involve +2 frameshifts, predominantly found in dsDNA viruses. Antisense overlaps in which one of the ORFs was encoded in the same frame on the opposite strand (−0) tend to be longer. Next, we develop a new graph-based representation of the distribution of overlaps among the ORFs of genomes in a given virus family. In the absence of an unambiguous partition of ORFs by homology at this taxonomic level, we used an alignment-free k-mer based approach to cluster protein coding sequences by similarity. We connect these clusters with two types of directed edges to indicate (1) that constituent ORFs are adjacent in one or more genomes, and (2) that these ORFs overlap. These adjacency graphs not only provide a natural visualization scheme, but also a novel statistical framework for analyzing the effects of gene- and genome-level attributes on the frequencies of overlaps.

APA, Harvard, Vancouver, ISO, and other styles

44

Zhang, Zhiyuan, Xia Feng, and Weigang Huo. "An improvement of PLSA-based community detection algorithm." Modern Physics Letters B 28, no. 15 (June 17, 2014): 1450120. http://dx.doi.org/10.1142/s0217984914501206.

Full text

Abstract:

Community detection is an important task in analyzing some real-world complex networks such as social networks and biological networks and draws lots of attention. PLSA-based community detection algorithm is a popular statistical approach for finding overlapping communities. It uses a probabilistic model for link graphs and can automatically find overlapping communities in both synthetic and real-world networks. However, sometimes PLSA community detection model may find separated communities with no connections linking them at all. This paper introduces a new iteration equation to improve it. We also use a simple merging method to determine an appropriate community number which should be specified in PLSA model in advance. Experiments on four real-world networks show that our improved equation can find specified number of communities for most times.

APA, Harvard, Vancouver, ISO, and other styles

45

PRATAP, ABHAY, SETU TALIYAN, and TIRATHA RAJ SINGH. "NMDB: NETWORK MOTIF DATABASE ENVISAGED AND EXPLICATED FROM HUMAN DISEASE SPECIFIC PATHWAYS." Journal of Biological Systems 22, no. 01 (March 2014): 89–100. http://dx.doi.org/10.1142/s0218339014500053.

Full text

Abstract:

The study of network motifs for large number of networks can aid us to resolve the functions of complex biological networks. In biology, network motifs that reappear within a network more often than expected in random networks include negative autoregulation, positive autoregulation, single-input modules, feedforward loops, dense overlapping regulons and feedback loops. These network motifs have their different dynamical functions. In this study, our main objective is to examine the enrichment of network motifs in different biological networks of human disease specific pathways. We characterize biological network motifs as biologically significant sub-graphs. We used computational and statistical criteria for efficient detection of biological network motifs, and introduced several estimation measures. Pathways of cardiovascular, cancer, infectious, repair, endocrine and metabolic diseases, were used for identifying and interlinking the relation between nodes. 3–8 sub-graph size network motifs were generated. Network Motif Database was then developed using PHP and MySQL. Results showed that there is an abundance of autoregulation, feedforward loops, single-input modules, dense overlapping regulons and other putative regulatory motifs in all the diseases included in this study. It is believed that the database will assist molecular and system biologists, biotechnologists, and other scientific community to encounter biologically meaningful information. Network Motif Database is freely available for academic and research purpose at: http://www.bioinfoindia.org/nmdb .

APA, Harvard, Vancouver, ISO, and other styles

46

Pattabiraman, Bharath, Md Mostofa Ali Patwary, Assefaw H. Gebremedhin, Wei-keng Liao, and Alok Choudhary. "Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection." Internet Mathematics 11, no. 4-5 (May 13, 2015): 421–48. http://dx.doi.org/10.1080/15427951.2014.986778.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

NEDJAH, NADIA, and LUIZA DE MACEDO MOURELLE. "PATTERN MATCHING CODE MINIMIZATION IN REWRITING-BASED PROGRAMMING LANGUAGES." International Journal of Foundations of Computer Science 13, no. 06 (December 2002): 873–87. http://dx.doi.org/10.1142/s0129054102001515.

Full text

Abstract:

We compile pattern matching for overlapping patterns in term rewriting systems into a minimal, tree matching automata. The use of directed acyclic graphs that shares all the isomorphic subautomata allows us to reduce space requirements. These are duplicated in the tree automaton. We design an efficient method to identify such subautomata and avoid duplicating their construction while generating the dag automaton. We compute some bounds on the size of the automata, thereby improving on previously known equivalent bounds for the tree automaton.

APA, Harvard, Vancouver, ISO, and other styles

48

WATTS, JAMESON K. M., and KENNETH W. KOPUT. "Supple networks: Preferential attachment by diversity in nascent social graphs." Network Science 2, no. 3 (November 10, 2014): 303–25. http://dx.doi.org/10.1017/nws.2014.21.

Full text

Abstract:

AbstractA preference for diversity has been identified as an important predictor of tie formation in certain networks, both social and organizational, that also exhibit a high degree of suppleness–the ability to retain their general form and character under stress (Durkheim, 1893/1997. The division of labor in society; Powell et al., 1996. Administrative Science Quarterly 116–145; Powell et al., 2005. American Journal of Sociology, 110(4), 1132–1205; Koput & Gutek, 2010. Gender stratification in the IT industry: Sex, status and social capital. Edward Elgar Publishing). Extant models of preferential attachment, based on popularity, similarity, and cohesion, meanwhile, produce exceedingly brittle networks (Albert et al., 2000. Nature, 406(6794), 378–382; Callaway et al., 2000. Physical Review Letters, 85(25), 5468–5471; Holme et al., 2002. Physical Review E, 65(2), 026107; Shore et al., 2013 Social Networks, 35(1), 116–123). A model of preferential attachment based on diversity is introduced and simulated, demonstrating that a preference for diversity can create a structure characterized by suppleness. This occurs because a preference for diversity promotes overlapping and redundant weak ties during the early stages of network formation.

APA, Harvard, Vancouver, ISO, and other styles

49

Dinç, Erdal, and Eda Büker. "A New Application of Continuous Wavelet Transform to Overlapping Chromatograms for the Quantitative Analysis of Amiloride Hydrochloride and Hydrochlorothiazide in Tablets by Ultra-Performance Liquid Chromatography." Journal of AOAC INTERNATIONAL 95, no. 3 (May 1, 2012): 751–56. http://dx.doi.org/10.5740/jaoacint.sge_dinc.

Full text

Abstract:

Abstract A new application of continuous wavelet transform (CWT) to overlapping peaks in a chromatogram was developed for the quantitative analysis of amiloride hydrochloride (AML) and hydrochlorothiazide (HCT) in tablets. Chromatographic analysis was done by using an ACQUITY ultra-performance LC (UPLC) BEH C18 column (50 × 2.1 mm id, 1.7 μm particle size) and a mobile phase consisting of methanol–0.1 M acetic acid (21 + 79, v/v) at a constant flow rate of 0.3 mL/min with diode array detection at 274 nm. The overlapping chromatographic peaks of the calibration set consisting of AML and HCT mixtures were recorded rapidly by using an ACQUITY UPLC H-Class system. The overlapping UPLC data vectors of AML and HCT drugs and their samples were processed by CWT signal processing methods. The calibration graphs for AML and HCT were computed from the relationship between concentration and areas of chromatographic CWT peaks. The applicability and validity of the improved UPLC-CWT approaches were confirmed by recovery studies and the standard addition technique. The proposed UPLC-CWT methods were applied to the determination of AML and HCT in tablets. The experimental results indicated that the suggested UPLC-CWT signal processing provides accurate and precise results for industrial QC and quantitative evaluation of AML-HCT tablets.

APA, Harvard, Vancouver, ISO, and other styles

50

Chen, Zhongliang, Feng Yuan, Xiaohui Li, Xiang Wang, He Li, Bangcai Wu, and Yuheng Chen. "Knowledge Extraction and Quality Inspection of Chinese Petrographic Description Texts with Complex Entities and Relations Using Machine Reading and Knowledge Graph: A Preliminary Research Study." Minerals 12, no. 9 (August 26, 2022): 1080. http://dx.doi.org/10.3390/min12091080.

Full text

Abstract:

(1) Background: Geological surveying is undergoing a digital transformation process towards the adoption of intelligent methods in China. Cognitive intelligence methods, such as those based on knowledge graphs and machine reading, have made progress in many domains and also provide a technical basis for quality detection in unstructured lithographic description texts. (2) Methods: First, the named entities and the relations of the domain-specific knowledge graph of petrography were defined based on the petrographic theory. Second, research was carried out based on a manually annotated corpus of petrographic description. The extraction of N-ary and single-entity overlapping relations and the separation of complex entities are key steps in this process. Third, a petrographic knowledge graph was formulated based on prior knowledge. Finally, the consistency between knowledge triples extracted from the corpus and the petrographic knowledge graph was calculated. The 1:50,000 sheet of Fengxiangyi located in the Dabie orogenic belt was selected for the empirical research. (3) Results: Using machine reading and the knowledge graph, petrographic knowledge can be extracted and the knowledge consistency calculation can quickly detect description errors about textures, structures and mineral components in petrographic description. (4) Conclusions: The proposed framework can be used to realise the intelligent inspection of petrographic knowledge with complex entities and relations and to improve the quality of petrographic description texts effectively.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Overlapping graphs'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles