Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Influence maximization method based on multi-layer potential and community structure

A technology with maximum impact and community, applied in data processing applications, instruments, calculations, etc., to achieve high accuracy and high efficiency

Inactive Publication Date: 2017-03-22
CHONGQING UNIV
View PDF0 Cites 2 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

The algorithm has not been verified under the existing independent cascade model or linear threshold model

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Influence maximization method based on multi-layer potential and community structure
  • Influence maximization method based on multi-layer potential and community structure
  • Influence maximization method based on multi-layer potential and community structure

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0030] Preferred embodiments of the present invention are described in detail below.

[0031] Without loss of generality, an undirected and unweighted graph is defined as G=(V,E,W), where V is the node set, E is the edge set, and W is the link weight of the corresponding edge. For graph G, it can be represented by an adjacency matrix A, as follows:

[0032]

[0033] For any node v in the graph, its neighbor node set is expressed as:

[0034] N(v)={u|W v,u >0} (2)

[0035] In the present invention, the IC (Independent Cascade) model is used, and for graph G (V, E, W), the activation weight of node u to v is defined as p uv as follows:

[0036]

[0037] From this, it can be obtained that for the unweighted graph G(V,E), the activation weight of node u to node v is k v Indicates the degree of v. Further define the community structure of graph G as the division of nodes in graph G={C 1 ,C 2 ,...,C k};∪ i C i =V; C i ∩C j =Φ, where the i-th community C i Con...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to an influence maximization method based on the multi-layer potential and community structure. According to the method, the influence propagation has two stages: multi-layer-potential-based expansion between communities at a first stage and influence propagation in communities at a second stage. To be specific, at the first stage, a seed node v tries to activate a neighbour node in a non-activated state, wherein the neighbour node is expresses as follows: {u|u belonging to N(v), active(u)=0}; the activated node during the process is marked as S1 (shown as a formula), wherein N(S) meets the following formula: N(S)=U(v belonging to S) N(v); and the S1 tries to activate another neighbour node in a non-activated state again, wherein the neighbour node is expresses as follows: {u|u belonging to N(S1)\S, activate(u)=0}, wherein the activated node is marked as S2. At the second stage, for a node expressed by a condition that any v belongs to the S2, the influence range of the node is limited in a communication where the node is located; for any communication Ci belonging to C, the influence scale depends on two factors: the value |Ci| of the community Ci and the numbe being intersection of the S2 and the Ci of the nodes, falling into the community, of the S2. According to the influence maximization method disclosed by the invention, the efficiency and the accuracy of the method are higher than thoes of the existing latest algorithms like an IPA algorithm and other heuristic algorithms.

Description

technical field [0001] The invention belongs to the field of computer data mining, and in particular relates to a method for quickly solving the problem of maximizing influence by utilizing a community structure, and in particular relates to the problem of maximizing influence in a large-scale network. Background technique [0002] Influence Maximization is an optimization problem about propagation. Whether it is the effective promotion of a company's new product or a certain concept, or the effective control of a certain virus or disaster, or other similar issues, it is inevitable to consider such a problem, how to use limited resources to achieve best results. Abstract in mathematical language is: for a given network G(V,E,W), (where V represents the set of nodes in the graph, E represents the set of edges in the graph, and W is the edge from the edge set E to the node set The weight corresponding to the mapping of the node pairs of V) Find a set S composed of k seed nod...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06Q50/00
CPCG06Q50/01
Inventor 尚家兴武红春周尚波林晓然齐颖许冶金
Owner CHONGQING UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com