共查询到20条相似文献，搜索用时 165 毫秒
1.
《Information processing & management》2020,57(2):102054
Social networks and many other graphs are attributed, meaning that their nodes are labelled with textual information such as personal data, expertise or interests. In attributed graphs, a common data analysis task is to find subgraphs whose nodes contain a given set of keywords. In many applications, the size of the subgraph should be limited (i.e., a subgraph with thousands of nodes is not desired). In this work, we introduce the problem of compact attributed group (AG) discovery. Given a set of query keywords and a desired solution size, the task is to find subgraphs with the desired number of nodes, such that the nodes are closely connected and each node contains as many query keywords as possible. We prove that finding an optimal solution is NP-hard and we propose approximation algorithms with a guaranteed ratio of two. Since the number of qualifying AGs may be large, we also show how to find approximate top-k AGs with polynomial delay. Finally, we experimentally verify the effectiveness and efficiency of our techniques on real-world graphs. 相似文献
2.
This paper studies mathematical properties of h-index sequences as developed by Liang [Liang, L. (2006). h-Index sequence and h-index matrix: Constructions and applications. Scientometrics,69(1), 153–159]. For practical reasons, Liming studies such sequences where the time goes backwards while it is more logical to use the time going forward (real career periods). Both type of h-index sequences are studied here and their interrelations are revealed. We show cases where these sequences are convex, linear and concave. We also show that, when one of the sequences is convex then the other one is concave, showing that the reverse-time sequence, in general, cannot be used to derive similar properties of the (difficult to obtain) forward time sequence. We show that both sequences are the same if and only if the author produces the same number of papers per year. If the author produces an increasing number of papers per year, then Liang’s h-sequences are above the “normal” ones. All these results are also valid for g- and R-sequences. The results are confirmed by the h-, g- and R-sequences (forward and reverse time) of the author. 相似文献
3.
One of the best known measures of information retrieval (IR) performance is the F-score, the harmonic mean of precision and recall. In this article we show that the curve of the F-score as a function of the number of retrieved items is always of the same shape: a fast concave increase to a maximum, followed by a slow decrease. In other words, there exists a single maximum, referred to as the tipping point, where the retrieval situation is ‘ideal’ in terms of the F-score. The tipping point thus indicates the optimal number of items to be retrieved, with more or less items resulting in a lower F-score. This empirical result is found in IR and link prediction experiments and can be partially explained theoretically, expanding on earlier results by Egghe. We discuss the implications and argue that, when comparing F-scores, one should compare the F-score curves’ tipping points. 相似文献
4.
In this paper, we propose a novel method for addressing the multi-equilibria consensus problem for a network of n agents with dynamics evolving in discrete-time. In this method, we introduce, for the first time in the literature, two concepts called primary and secondary layer subgraphs. Then, we present our main results on directed graphs such that multiple consensus equilibria states are achieved, thereby extending the existing single-state consensus convergence results in the literature. Furthermore, we propose an algorithm to determine the number of equilibria for any given directed graph automatically by a computer program. We also analyze the convergence properties of multi-equilibria consensus in directed networks with time-delays under the assumption that all delays are bounded. We show that introducing communication time-delays does not affect the number of equilibria of the given network. Finally, we verify our theoretical results via numerical examples. 相似文献
5.
Sequences of integers are common data types, occurring either as primary data or ancillary structures. The sizes of sequences can be large, making compression an interesting option. Effective compression presupposes variable-length coding, which destroys the regular alignment of values. Yet it would often be desirable to access only a small subset of the entries, either by position (ordinal number) or by content (element value), without having to decode most of the sequence from the start. Here such a random access technique for compressed integers is described, with the special feature that no auxiliary index is needed. The solution applies a method called interpolative coding, which is one of the most efficient non-statistical codes for integers. Indexing is avoided by address calculation guaranteeing sufficient space for codes even in the worst case. The additional redundancy, compared to regular interpolative coding, is only about 1 bit per source integer for uniform distribution. The time complexity of random access is logarithmic with respect to the source size for both position-based and content-based retrieval. According to experiments, random access is faster than full decoding when the number of accessed integers is not more than approximately 0.75 · n/log2n for sequence length n. The tests also confirm that the method is quite competitive with other approaches to random access coding, suggested in the literature. 相似文献
6.
Donald L. Margolis 《Journal of The Franklin Institute》1979,308(3):255-268
A procedure is presented whereby the control volume equations for one-dimensional, compressible gas dynamics are cast into first-order, state variable form. These equations are interpreted using causal bond graphs. The resulting bond graph is shown to reduce to the classic I-C chain under acoustic constraints and to a more recently developed model of low speed thermal energy transport subject to associated constraints.Through example it is demonstrated that the control volume bond graph is easily coupled to an overall system model and thus can be digitally simulated as part of the overall nonlinear state space representation. The result is that a very accurate gas dynamic model can be coupled with an overall dynamic system model without requiring a prohibitively large number of equations. 相似文献
7.
This paper investigates a distributed optimization problem over multi-agent networks subject to both local and coupled constraints in a non-stationary environment, where a set of agents aim to cooperatively minimize the sum of locally time-varying cost functions when the communication graphs are time-changing connected and unbalanced. Based on dual decomposition, we propose a distributed online dual push-sum learning algorithm by incorporating the push-sum protocol into dual gradient method. We then show that the regret bound has a sublinear growth of O(Tp) and the constraint violation is also sublinear with order of where T is the time horizon and 0 < p ≤ 1/2. Finally, simulation experiments on a plug-in electric vehicle charging problem are utilized to verify the performance of the proposed algorithm. The proposed algorithm is adaptive without knowing the total number of iterations T in advance. The convergence results are established on more general unbalanced graphs without the boundedness assumption on dual variables. In addition, more privacy concerns are guaranteed since only dual variables related with coupled constraints are exchanged among agents. 相似文献
8.
Using data generated by progressive nucleation mechanism on the cumulative fraction of citations of individual papers published successively by a hypothetical author, an expression for the time dependence of the cumulative number Lsum(t) of citations of progressively published papers is proposed. It was found that, for all nonzero values of constant publication rate ΔN, the cumulative citations Lsum(t) of the cumulative N papers published by an author in his/her entire publication career spanning over T years may be represented in distinct regions: (1) in the region 0 < t < Θ0 (where Θ0 ≈ T/3), Lsum(t) slowly increases proportionally to the square of the citation time t, and (2) in the region t > Θ0, Lsum(t) approaches a constant Lsum(max) at T. In the former region, the time dependence of Lsum(t) of an author is associated with three parameters, viz. the citability parameter λ0, the publication rate ΔN and his/her publication career t. Based on the predicted dependence of Lsum(t) on t, a useful scientometric age-independent measure, defined as citation acceleration a = Lsum(t)/t2, is suggested to analyze and compare the scientific activities of different authors. Confrontation of the time dependence of cumulative number Lsum(t) of citations of papers with the theoretical equation reveals one or more citation periods during the publication careers of different authors. 相似文献
9.
We present a comparative study of four impact measures: the h-index, the g-index, the R-index and the j-index. The g-index satisfies the transfer principle, the j-index satisfies the opposite transfer principle while the h- and R-indices do not satisfy any of these principles. We study general inequalities between these measures and also determine their maximal and minimal values, given a fixed total number of citations. 相似文献
10.
《Information processing & management》2023,60(3):103297
Humans are able to reason from multiple sources to arrive at the correct answer. In the context of Multiple Choice Question Answering (MCQA), knowledge graphs can provide subgraphs based on different combinations of questions and answers, mimicking the way humans find answers. However, current research mainly focuses on independent reasoning on a single graph for each question–answer pair, lacking the ability for joint reasoning among all answer candidates. In this paper, we propose a novel method KMSQA, which leverages multiple subgraphs from the large knowledge graph ConceptNet to model the comprehensive reasoning process. We further encode the knowledge graphs with shared Graph Neural Networks (GNNs) and perform joint reasoning across multiple subgraphs. We evaluate our model on two common datasets: CommonsenseQA (CSQA) and OpenBookQA (OBQA). Our method achieves an exact match score of 74.53% on CSQA and 71.80% on OBQA, outperforming all eight baselines. 相似文献
11.
The induced matching partition number of graph G is the minimum integer k such that there exists a k-partition (V1,V2,…Vk) of V(G) such that,for each i(1≤i≤k),G[Vi]is 1-regular.In this paper,we study the induced matching partition number of product graphs. We provide a lower bound and an upper bound for the induced matching partition number of product graphs, and exact results are given for some special product graphs. 相似文献
12.
Each graph may be associated with a certain function called its generic form. If one knows the generic forms of given graphs, then one can easily determine the number of spanning trees in graphs obtained from a complete multi-graph either (1) by adding, or (2) by deleting the edges of disjoint copies of the given graphs. Our obejective here is to give a proof of a simple and useful relation between the generic forms of graphs that are complementary with respect to a complete multi-graph. 相似文献
13.
网络结构与创新扩散研究 总被引：1，自引：0，他引：1
根据WS小世界模型的思想，构建了从规则网络到随机网络的一系列扩散网络图，通过虚拟采纳个体的决策过程，研究了网络结构与性质对创新微观采纳和宏观扩散的影响。不同于已往的研究，本文将创新采纳与创新扩散统一起来，运用复杂网络的方法，研究了网络结构与创新扩散之间的动态相互关系。数值模拟结果表明：存在介于规则网络和随机网络之间的小世界扩散网络；外部因素和内部因素共同决定一个成功的扩散过程；网络的簇系数决定扩散的最终水平，而网络平均距离决定扩散速度；网络个体间的异质性程度越大，越不利于创新扩散。 相似文献
14.
Chien-Chun Kung 《Journal of The Franklin Institute》2008,345(8):851-876
In this paper, an analytic solution of nonlinear H∞ robust controller is first proposed and used in a complete six degree-of-freedom nonlinear equations of motion of flight vehicle system with mass and moment inertia uncertainties. A special Lyapunov function with mass and moment inertia uncertainties is considered to solve the associated Hamilton-Jacobi partial differential inequality (HJPDI). The HJPDI is solved analytically, resulting in a nonlinear H∞ robust controller with simple proportional feedback structure. Next, the control surface inverse algorithm (CSIA) is introduced to determine the angles of control surface deflection from the nonlinear H∞ control command. The ranges of prefilter and loss ratio that guarantee stability and robustness of nonlinear H∞ flight control system implemented by CSIA are derived. Real aerodynamic data, engine data and actuator system of F-16 aircraft are carried out in numerical simulations to verify the proposed scheme. The results show that the responses still keep good convergence for large initial perturbation and the robust stability with mass and moment inertia uncertainties in the permissible ranges of the prefilter and loss ratio for which this design guarantees stability give same conclusion. 相似文献
15.
The discovery of new drugs is often propelled by the increasing resistance of parasites to existing drugs and the availability of better technology platforms. The area of microfluidics has provided devices for faster screening of compounds, controlled sampling/sorting of whole animals, and automated behavioral pattern recognition. In most microfluidic devices, drug effects on small animals (e.g., Caenorhabditis elegans) are quantified by an end-point, dose response curve representing a single parameter (such as worm velocity or stroke frequency). Here, we present a multi-parameter extraction method to characterize modes of paralysis in C. elegans over an extended time period. A microfluidic device with real-time imaging is used to expose C. elegans to four anthelmintic drugs (i.e., pyrantel, levamisole, tribendimidine, and methyridine). We quantified worm behavior with parameters such as curls per second, types of paralyzation, mode frequency, and number/duration of active/immobilization periods. Each drug was chosen at EC75 where 75% of the worm population is responsive to the drug. At equipotent concentrations, we observed differences in the manner with which worms paralyzed in drug environments. Our study highlights the need for assaying drug effects on small animal models with multiple parameters quantified at regular time points over an extended period to adequately capture the resistance and adaptability in chemical environments. 相似文献
16.
Bond graphs are an extremely useful modeling procedure for representing the actual energy exchange mechanisms of interacting dynamic systems. Governing state equations are straightforwardly obtained from the bond graph; however, for large structures, a restrictively large number of equations can result. A procedure is developed whereby the original equations are reduced to a form suitable for modal decomposition. The resulting modes are reinterpreted in bond graph form with the resulting model being an extremely accurate system representation while requiring only a fraction of the original number of equations. The procedure is demonstrated through example. 相似文献
17.
Diomidis S. Michalopoulos George K. Karagiannidis 《Journal of The Franklin Institute》2008,345(7):723-728
In this paper, we provide closed-form expressions for the symbol error probability of decode and forward cooperative diversity systems, when operating over independent but not necessarily identically distributed Nakagami-m fading channels. The results hold for arbitrary number of relays, and refer to the M-ary QAM and M-ary PSK modulations. 相似文献
18.
In this paper, a Generalized Cluster Centroid based Classifier (GCCC) and its variants for text categorization are proposed by utilizing a clustering algorithm to integrate two well-known classifiers, i.e., the K-nearest-neighbor (KNN) classifier and the Rocchio classifier. KNN, a lazy learning method, suffers from inefficiency in online categorization while achieving remarkable effectiveness. Rocchio, which has efficient categorization performance, fails to obtain an expressive categorization model due to its inherent linear separability assumption. Our proposed method mainly focuses on two points: one point is that we use a clustering algorithm to strengthen the expressiveness of the Rocchio model; another one is that we employ the improved Rocchio model to speed up the categorization process of KNN. Extensive experiments conducted on both English and Chinese corpora show that GCCC and its variants have better categorization ability than some state-of-the-art classifiers, i.e., Rocchio, KNN and Support Vector Machine (SVM). 相似文献
19.
Joy Iong-Zong Chen 《Journal of The Franklin Institute》2005,342(6):638-656
Ordered statistics is applied in this paper to analyze the performance of ordered selection combining schemes with different modulation receptions operating in Nakagami-m fading environments. The ordered selection combining will be adapted to include the conventional selection combining (SC), the second-order diversity combining (SC-2), and the third-order diversity combining (SC-3). All the results are validated by comparing the special case Rayleigh distribution with the fading figure m=1 in the Nakagami-m distribution. The results show that SC is in performance the worst in both coherent and non-coherent schemes, as expected. The performance differences between SC-2 and MRC, and SC-3 and EGC are not significant when the diversity order L?3, but the differences will increase when L?5. 相似文献
20.
Uniform upper bound of the second largest eigenvalue of stochastic matrices with equal-neighbor rule
Given the number of vertices only, we provide a uniform upper bound of the second largest eigenvalue (SLE) of stochastic matrices induced from rooted graphs under the equal-neighbor rule, by acquiring a tight upper bound of its scrambling constant (SC). Furthermore, with the concept of canonical form of rooted graphs, we find the least connective topology of rooted graphs in the sense of SC. When more information on the graph topology is available, a more accurate bound is also provided. Our result is applied to estimate the convergence rate of consensus protocols studied in system and control literature. 相似文献