Mike Coulson

Eric Dantras
email: eric.dantras@univ-tlse3.fr

Philippe Olivier

Nathalie Gleizes

Colette Lacabanne

Thermal conductivity and diffusivity of carbon-reinforced polyetherketoneketone composites

Keywords: CFRP, diffusivity, PEKK, thermal conductivity

 (at 25 C, polymers thermal diffusivity is between 0.05 and 0.3 mm 2 s -127-31 ). Within available literature, it appears as if these parameters may have not been studied in the case of PEKK.

 Choy et al. 21 studied the diffusivity of PEEK/short-carbon fiber composites and obtained values between 0.7 and 1 mm 2 s -1 at 50 C; this greater diffusivity has been attributed to the random orientation of the short fibers.

INTRODUCTION

The use of carbon in polymer composite is recurrent for the improvement of specific properties. [1][2][3][4] Carbon fibers (CFs) are often used as mechanical reinforcement for polymer composite. [5][6][7][8] Polyetherketoneketone (PEKK)/CF composites could be attractive structural materials if the automation of the processing is possible. The most promising technology for realizing future parts for aero-nautics and space is the automated fiber placement technology with laser heating. A tape of carbon fiber impregnated with PEKK pow-der was developed to be deposited by a fiber placement robot. Dur-ing this deposit, it will be important to understand heat transport phenomena in such complex materials. Thermal conductivity and thermal diffusivity are widely studied in the field of polymers and their composites. [9][10][11][12][13][14][15] Several works were devoted to the temperature depen-dence of thermal conductivity and thermal diffusivity of polymer composites. [16][17][18][19] In polymer composites, a decrease in the thermal dif-fusivity and an increase in thermal conductivity with the increase in temperature were observed. 10,[START_REF] Rivière | Analyse des mécanismes de conduction thermique dans les composites stucturaux PEEK:particles submicroniques d'argent[END_REF][START_REF] Choy | [END_REF][22][23][24] The introduction of fillers modifies the thermal properties of polymers. The composite shows thermal conductivity and thermal diffusivity higher than for the polymer. 15,25 Scant information is available on polyaryletherketone (PAEK) stud-ies; however, Choy et al. on PEEK/short-fiber composites obtained a thermal conductivity of 0.02 W.m -1 .K -1 for PEEK at 25 C and increase in conductivity as a function of temperature was EXPERIMENTAL Materials Polyetherketoneketone. PEKK KEPSTAN (Figure 1) was supplied by ARKEMA France in powder (20 μm).

Physical properties of PEKK are defined by terephtalic/isophtalic precursor ratio (T/I ratio). PEKK KEPSTAN presents a 70/30 T/I ratio.

Carbon Fillers. Glassy carbon. The vitreous carbon from Sigma-Aldrich (Saint Louis, Missouri, USA) is 99.95% pure with spherical particles averaging 12 μm in diameter. It was made by the pyrolysis of furfuryl alcohol. 37 We thus had model samples with controlled aspect ratio fillers and variable volume fractions.

Carbon Fiber. Unidirectional carbon fibers Toray's Torayca T700 were used. Fibers were used unsized. T700 fibers with a carbon content of 93%, 38 possess high mechanical properties, showing a tensile modulus of 135 GPa.

Composite Preparation. PEKK/glassy carbon composites. PEKK and GC were dispersed in ethanol by sonication for obtaining dispersion. After evaporation of the solvent, the powder was molded at 370 C. Composites with volume fractions comprised between 5% and 45% in volume were prepared.

PEKK/CF composites. After impregnation, composites with a 40 vol % of PEKK were obtained. A "reference" PEKK/CF composite was realized by draping and consolidation in autoclave. Other PEKK/CF composites were prepared by automated placement fibers. After the laser deposit, a PEKK/CF composite was obtained with a mechanical strength. Porosity could remain inside composites, which imply an additional consolidation step after deposit (autoclave/hot press).

Methods

Guarded Hot Plates Method: Thermal Conductivity. The thermal conductivity was measured using the guarded hot plates method. The main advantage of this technique is that the thermal conductivity is deduced from the Fourier equation: an accuracy of 5% is obtained. The measure does not involve density that cannot be determined with a good accuracy in heterogeneous materials like composites. A stationary unidirectional heat flow was created within the sample. All the assembly was equilibrated by the guard at the temperature of the measurement. The thermal resistance of the sample was determined using the relation 1:

R Sample = F T u -T m T u -T l -R cal ð1Þ
where R sample is the thermal resistance of the sample, R cal is the thermal resistance of the calorimeter, and F is the calibration factor of the device. The three temperatures correspond, respectively, to T u (upper plate temperature), T l (the lower plate temperature), and T m (temperature of the material). The thermal conductivity λ is then determined from eq. ( 2):

λ = e R sample ð2Þ
where e is the sample thickness. The device used is the DTC 300 thermal conductivity meter from thermal analysis instrument.

The disk-shaped samples have a diameter of 50 mm and a thickness of 2 mm. In order to optimize the heat transfer through the sample, it is covered with a thermal paste (silicone/alumina), which improves the contact with the plates. The measurements were performed during heating by temperature step. A change of standard must be carried out at 100 C, so it is not possible to carry out continuous measurements from ambient to high temperatures. The measurements were performed under air at 25 C, and then from 140 C to 230 C by steps of 10 . The high temperature range was chosen in order to be as close as possible to the conditions of implementation of the CFRP. However, the limits of the equipment and the used thermal paste imposed a maximum temperature of 230 C.

Laser Flash Method: Thermal Diffusivity. The Laser Flash method is the only one that allows us to reach thermal diffusivity. The Laser Flash Analyzer LFA 447 from Netzsch 39 was used. A hotplate disposed in the sample holder encouraged measurement at the desired temperature. A laser pulse is then sent to the lower face of the sample and the infrared detector located on the upper face transmitted the temperature signal of the sample as a function of time. The samples were squares of 10 mm × 2-4 mm thick. The thermal diffusivity measurements were performed on PEKK/glassy carbon and PEKK/CF composites at a temperature of 50 C with 20 C increments up to 270 C. The measurements were performed under air.

RESULTS AND DISCUSSION

Thermal Conductivity of PEKK/Glassy Carbon Composites Influence of Glassy Carbon Volume Fraction. Carbon glassy particles, with an aspect ratio (ξ) close to 1, are shown in Figure 2.

The evolution of the thermal conductivity λ of PEKK/GC composites is measured at 25 C as a function of carbon volume fraction (Figure 3). Carbon volume fractions were chosen between 0 vol % and 45 vol % to study the thermal behavior from low-volume fraction to volume fraction as close as possible to CFs volume fraction of PEKK/CF composite. For PEKK/GC composite, 45 vol % glassy carbon is the limit. Above this value, the composite is brittle and cannot be processed for measurements. The measurements are performed three times for each sample; the values reported in Figure 3 are the average of the three measurements.

The thermal conductivity of PEKK is 0.178 W.m -1 .K -1 . This value is consistent with those reported in the literature for different polymers: around 0.2 W.m -1 .K -1 at room temperature. [START_REF] Choy | [END_REF]39 It should be noted that it is close to PEEK value [START_REF] Rivière | Analyse des mécanismes de conduction thermique dans les composites stucturaux PEEK:particles submicroniques d'argent[END_REF] (0.24 W.m -1 .K -1 ).

The introduction of vitreous carbon into the PEKK matrix results in an increase of thermal conductivity. This complex behavior will be described by analog models. This analysis will be presented later in the section on isotherm analog models. For the PEKK/GC composites with the highest content (45 vol % of carbon), a value of 0.716 W.m -1 .K -1 is reached. The increase in thermal conductivity with the introduction of glassy carbon is low compared to the values reported in the literature, for a compacted powder of glassy carbon 22 : between 4 and 6 W.m -1 .K -1 .

Thermomechanical History Effect of PEKK/CFs Composites.

The PEKK/CF samples were studied by the guarded hot plate method at 25 C. The conductivity values for these samples are reported in Table I.

A PEKK/CF composite realized by a draping and consolidation in autoclave was used as reference to evaluate the quality of the composites produced by laser deposit. For this "reference PEKK/CF" composite, a value of 0.654 W.m -1 .K -1 is indicated. This value is considered as the optimum conductivity value obtainable, according to our data, with this type of PEKK/CF composite. In Table I, measurements were made on a nonconsolidated sample (after laser deposit) and on a consolidated sample by hot press. Composites produced by laser deposit have a lower thermal conductivity than the reference composite, which implies a better consolidation of the reference composite.

In addition, the thermal conductivity of the composites increases with the level of consolidation with a conductivity of 0.283 W.m -1 . K -1 for the nonconsolidated composite and a value of 0.538 W. m -1 .K -1 for the hot-press consolidated composite. This result implies that the internal connectivity of the material plays a major role in heat transfer. Isothermal Analog Model. To better understand the thermal behavior of the PEKK/GC and PEKK/CF composites, the experimental points were compared to analog models. 40 The three models used, as well as the equation associated with λ (or K) for each model are shown in Figure 4.

Analog models take into account the orientation of the heat flux, the volume percentage of the two components (ν 1 and ν 2 ) and the thermal conductivity of the components (k 1 and k 2 ). 40 The values k 2 and ν 2 being associated with the most thermally conductive constituent, here the carbon filler (GC or CF). For all three models, the value of k 1 is 0.178 W.m -1 .K -1 (measured value for PEKK) and the value of k 2 is 4 W.m -1 .K -1 for GC and 21 W.m -1 . K -1 for CFs. [START_REF] Pierson | Handbook of Carbon, Graphite, Diamond and Fullerenes: Properties[END_REF] The parallel model corresponds to a succession of polymer layers and carbon stacked on each other; the measurement is carried out in the plane of the layers. The series model is also a succession of polymer and carbon layers, but the measurement is performed in the direction perpendicular to the layers. The Maxwell-Eucken model corresponds to spherical particles (ξ = 1) dispersion in a matrix. This last model does not take into account interactions between particles so that it is more suited to low loading with well-dispersed fillers. The different analog models predictions, as well as the experimental points of the PEKK/GC and PEKK/CF composites, are plotted in Figure 5.

The parallel model is well above the experimental points, which is consistent with measurement along the longitudinal direction of the oriented layers. This case can be associated with polymer/CF composites by taking the measurement in the longitudinal direction of the fiber. In this study, this type of measurement is not feasible with these composites (quasi-iso multiplies); the device imposes the sampling geometry. The series model is below the experimental points corresponding to the PEKK/GC composites. The conductivity values of PEKK/pressed CF composites are close to the series model, which is consistent with transversal measurement of successive layers: PEKK and continuous carbon fibers.

Two series models were used: the first with k 2 = 4 W.m -1 .K -1 to compare the values with the composites PEKK/GC and the second k 2 = 21 W.m -1 .K -1 for PEKK/CF composite. The difference between the two models is weak, which implies that the thermal conductivity values depend mainly on the thermally insulating phase.

The filler volume fraction of the nonconsolidated PEKK/CF composite was evaluated at 44 vol %, taking into account the porosity determined by hydrostatic weighing at 27.3% AE 1%. Porosity values were also checked by X-ray tomography. By studying the gray levels, the porosity ratio has been determined. An overall porosity of 25.7% AE 3% is obtained for nonconsolidated PEKK/CF composite. This porosity rate is consistent with the result obtained by hydrostatic weighing measurement.

Non-consolidated PEKK/CF composite processed by laser deposit shows a behavior close to the series model, with a thermal conductivity of 0.283 W.m -1 .K -1 . The PEKK/CF sample prepared by laser deposit and hot pressed has a thermal conductivity of 0.538 W.m -1 .K -1 while remaining close to the series model. The thermal conductivity is higher for the reference composite with fiber, λ Ref = 0.654 W.m -1 .K -1 , which corresponds to a behavior closer to the Maxwell-Eucken model. For this composite, the porosity is determined by hydrostatic weighing at <1 vol %. But the higher value of conductivity cannot be explained only by a better consolidation which slightly increases the conductivity. In this case, the increase in thermal conductivity has been associated with a better distribution of the matrix between the fibers, which corresponds, in a 2D transverse model, to a disk dispersion in a matrix. Thus, there is an analogy with a dispersion of spherical particles, which explains the proximity of the experimental points to the Maxwell-Eucken model. In the case of composites developed by laser deposit, the lower thermal conductivity could be explained by a poor distribution of the matrix in the fibers which would give rise to differentiated layers of fibers and polymer (as in the case of the series model). Experimental points of the PEKK/GC are well described by the Maxwell-Eucken model, for low carbon volume fraction, which implies a good dispersion of the particles in the PEKK matrix. The higher thermal conductivity values for higher carbon content (> 20%) can be explained by the existence, among carbon particles, of contacts not taken into account by the model.

Evolution with Temperature

Fillers Volume Fraction Effect. The effect of the carbon particles introduction on the thermal conductivity behavior with temperature was studied on PEKK/GC composites. The measurements were performed on composites loaded between 0 vol % and 45 vol %, for temperatures between 25 and 250 C. Measurements are reproduced three times and the values shown in Figure 6 are the average of these three points.

Thermal conductivity increases slightly with temperature for all PEKK/GC composites. This type of behavior has already been observed by Choy et al. on PEEK and PEEK/CF composites. [START_REF] Choy | [END_REF]39 On polymer matrix and carbon particle composites, Lin et al. and Hung et al. observed linear behaviors of thermal conductivity with temperature. [START_REF] Lin | [END_REF]43 We studied the evolution of thermal conductivity as a function of the particle ratio with empirical model. An affine relationship was used to describe our experimental points between 140 and 230 C (Figure 7).

Equations parameters describing the variation of thermal conductivity versus temperature are reported in Table II.

The evolution of the thermal conductivity versus temperature is directly related to the carbon volume fraction. Although there is a slight increase, the slope looks to be constant for the first three volume fraction and increases rapidly with increasing loading. Therefore, the slope increase could be related to contacts between spherical particles that favors heat transfer.

Thermodynamic History Effect. The temperature behavior was studied on PEKK/CF composites. The measurements made on the PEKK/CF reference composite and the PEKK/CF autoclave consolidated composite are shown in Figure 8. A porosity of 4% for both samples was determined by hydrostatic weighing.

A monotonous increase is observed on the PEKK/CF composites in the studied temperature range. The difference in thermal conductivity between the two composites is due to the porosity of the PEKK/CF composite consolidated in autoclave and a better distribution of the polymer within the fibers in the reference composite.

Experimental points of the PEKK/CF composite consolidated in autoclave are described by a straight line with a slope of 5.80 × 10 -4 . The straight line describing points corresponding to the reference PEKK/CF has a slope of 6.39 × 10 -4 . It can be seen that for the same volume content of fibers, the slope increases slightly with the connectivity variation.

Although the thermal conductivity values obtained for the PEKK/CF composites are lower than those obtained for the most loaded PEKK/GC composites, the resulting slopes are higher. This confirms that the evolution of the conductivity is related to the amount of carbon in the composite, with a slope that increases with carbon volume fraction.

Thermal Diffusivity

Filler Volume Fraction Effect. The evolution of thermal diffusivity as a function of the carbon volume ratio has been studied. D is determined by the laser flash method for a temperature of 50 C. Measurements were carried out in duplicate for each sample, so the values shown in Figure 9 are the average of the two measurements.

A thermal diffusivity of 0.146 mm 2 .s -1 is obtained for PEKK alone. This value is in agreement with the literature on polymers 24,30,31 : thermal diffusivity, at ambient temperature, is between 0.15 and 0.2 mm 2 .s -1 with a value of 0.2 mm 2 .s -1 for PEEK. [START_REF] Choy | [END_REF] Introduction of carbon into the PEKK matrix led to an increase in thermal diffusivity. The diffusivity does not follow a linear variation: this complex behavior will described later by analog model. The PEKK/GC composite (45 vol % of carbon) reaches a value of 0.626 mm 2 .s -1 .

The increase in the thermal diffusivity by the addition of GC is rather weak considering the thermal diffusivity of a compacted powder of GC, which is reported in the literature 22 between 4 and 10 mm 2 .s -1 . Several PEKK/CF samples (40 vol % of PEKK) were studied by the laser flash method at 50 C. The diffusivity results for these samples are reported in Table III.

For the composite "PEKK/CF reference," a value of 0.603 mm 2 .s -1 is measured. This value is considered as the optimum diffusivity value obtainable with this type of PEKK composite. Measurements were also made on a PEKK/CF composite sample consolidated in autoclave. The samples produced by laser deposit have a thermal diffusivity lower than the reference composite, which implies a better consolidation of the reference composite. Thermal diffusivity, in the same way that the thermal conductivity, increases with the consolidation level. A diffusivity of 0.495 mm 2 .s -1 is obtained for the consolidated autoclave composite and a value of 0.603 mm 2 .s -1 is obtained for the reference composite. This implies that the internal connectivity of the material plays a major role in the speed of phonon diffusion.

Isothermal Analog Model. Analog models used for thermal conductivity were adapted to thermal diffusivity by keeping the volume percentage of the two constituents (ν 1 and ν 2 ) and replacing the thermal conductivity by the diffusivity (D 1 and D 2 ). The values D 2 and ν 2 being associated with the most thermally conductive constituent; here, the carbon (GC or CF). For all three models the value of D 1 is 0.146 mm 2 .s -1 (polymer value) and the value of D 2 is 6 mm 2 .s -1 . The different analog models, as well as the experimental thermal diffusivity points of the PEKK/GC and PEKK/CF composites, are shown in Figure 10.

The parallel model is well above our experimental points, as for thermal conductivity, the measurement is not in the longitudinal direction of oriented carbon layers. The series model is below the experimental points corresponding to PEKK/GC composites. The diffusivity values of PEKKCF hot pressed composites are close to the series model, which is consistent with transversal measurement of successive layers of PEKK and continuous carbon fibers. The laser-deposited composite shows a behavior close to the serial model, with the autoclaved PEKK/CF sample showing a thermal diffusivity of 0.495 mm 2 .s -1 and the hot-pressed PEKK/CF sample showing a thermal diffusivity of 0.517 mm 2 .s -1 . The higher thermal diffusivity for the reference composite with fiber, λ Ref = 0.603 mm 2 .s -1 , corresponds to a behavior closer to the Maxwell-Eucken model. This behavior is explained by a better consolidation and also by a better distribution of the matrix between the fibers which implies an homogeneous dispersion of disk (corresponding to carbon fiber seen in 2D). The case of spherical particle dispersion in a matrix can explain the proximity with the Maxwell-Eucken model. In the case of composites produced by laser deposit, the lower thermal diffusivity is explained by a poor distribution of the matrix in the fibers, which would give rise to differentiated layers of fiber and polymer (as in the case of the series model). The experimental points of the PEKK/GC are well described by the Maxwell-Eucken model which confirms that the dispersion of the particles within the PEKK matrix is good.

Evolution with Temperature Filler Content Effect. The effect of carbon particles on the PEKK thermal diffusivity was studied on the PEKK/GC composites as a function of temperature. The measurements were performed on composites loaded between 0 vol % and 45 vol %of carbon, for temperatures between 50 and 270 C. Measurements were carried out in duplicate and the values reported in Figures 11 are the average of these two sets of data.

Thermal diffusivity slowly decreases with temperature for all samples. A quasi-linear decrease in thermal diffusivity with temperature has already been observed for PEEK/carbon particle composites. 17,[START_REF] Choy | [END_REF] The increase in temperature induces a greater thermal agitation which causes a greater number of collisions between phonons. The concomitant decrease of the average free path results in a decrease of D. The slope increases gradually with the volume fraction of carbon used; to study this evolution an affine relationship was used. Analytical parameters describing the behavior of thermal diffusivity are reported in Table IV.

An increase in the absolute value of the slope is observed when increasing the amount of glassy carbon in the composite, which implies a stronger decrease of D with T. The increase in the amount of particles causes an increase in the number of interfaces which limits the average free path of the phonons: a faster decrease in the thermal diffusivity is thus easily explained.

Thermomechanical History Effect. The thermal diffusivity of consolidated PEKK/CF consolidated in autoclave and reference PEKK/CF composite were studied versus the temperature for three samples. Figure 12 shows the averages obtained for three samples.

The diffusivity values obtained for PEKK/CF (between 0.5 and 0.6 mm 2 s -1 at 50 C) are very close to those reported for epoxy/continuous CF composites (0.45-0.55 mm 2 s -1 at 50 C). [START_REF] Joven | SAMPE International Symposium and Proceedings[END_REF][START_REF] Da Silva | [END_REF][36] It is also interesting to note that the diffusivity values for PEKK/CF are slightly lower than the values obtained with PEEK/short-carbon fiber composites (0.7-1 mm 2 s -1 at 50 C). [START_REF] Choy | [END_REF] This difference has been attributed to the random orientation of the short fibers. As for spherical carbon particles, a monotonic decrease is observed on PEKK/CF composites in the temperature range studied. The experimental points of PEKK/CF composite consolidated in autoclave and the reference PEKK/CF are described by a affine equation with a slope of -9.15 × 10 -4 and -8.15 × 10 -4 , respectively.

Thermal diffusivity values, as well as the slope values, obtained for the PEKK/CF composites are lower than those obtained for the highest loading PEKK/GC composites. The lower diffusivity values are related to the transverse configuration of the fibers compared to measurement orientation. As for the slope values, they could be related to the interfacial resistances less important with the fibers than for the spherical particles.

CONCLUSION

In this study, the physical parameters associated with heat transfer have been studied for PEKK, PEKK/GC, and PEKK/CF composites. In PEKK/GC composites, thermal conductivity and diffusivity show an increase with the addition of carbon fillers. For low carbon ratio, the Maxwell-Eucken model indicates from experimental data that particles are well dispersed. For higher carbon ratio, experimental data are no more consistent with the Maxwell-Eucken model. This discrepancy might be explained by contacts between carbon particles, which are not taken into account by the model. The effect of porosity on conductivity and thermal diffusivity is strongly marked on PEKK/CF composites. The decrease in porosity causes an increase in thermal parameters: this evolution is due to an increase in the internal connectivity of the composite. The increase in λ and D implies other parameters than porosity. The reference PEKK/CF composite approaches the theoretical model of Maxwell-Eucken, which implies in a 2D transverse section, a homogeneous dispersion of disks in PEKK. Accordingly, it is important to emphasize that the thermal conductivity and diffusivity are dependent on the dispersion of fibers in PEKK/CF composites.

Figure 1 .

 1 Figure 1. Molecular structure of PEKK with para and meta links.

Figure 2 .Figure 3 . 538 Figure 4 .

 235384 Figure 2. SEM image of GC.

Figure 5 .Figure 6 .Figure 7 .

 567 Figure 5. Thermal conductivity λ, as a function of carbon volume fraction.The gray and black continuous lines correspond to the parallel and Maxwell-Eucken models respectively; the dashed and the dotted lines corresponds to the series 1 and series 2 models, respectively.

Figure 8 .Figure 9 .

 89 Figure 8. Thermal conductivity λ of PEKK/CF reference composites and PEKK/CF produced by laser deposit, as a function of temperature.

Figure 10 .Figure 11 .

 1011 Figure 10. Thermal diffusivity D as a function of the carbon volume content. The gray and black continuous lines correspond to the parallel and Maxwell-Eucken models respectively; the dashed line corresponds to the series model.

Figure 12 .

 12 Figure 12. Thermal diffusivity D of PEKK/CF composites as a function of temperature.

Table II .

 II Equations Parameters Describing the Behavior of λ as a Function of T

	λ = a.T + b	a (×10 -4 )	b
	PEKK	1.68	0.227
	PEKK/11% GC	1.70	0.302
	PEKK/19% GC	1.74	0.362
	PEKK/22% GC	2.08	0.376
	PEKK/33% GC	2.29	0.563
	PEKK / 45% GC	3.41	0.831

Table III .

 III Thermal Diffusivity D of PEKK/CFs Composites at 50 C

		PEKK/CF	PEKK/CF	PEKK/CF
		Reference	Autoclave	Pressed
	D (mm 2 .s -1 )	0.603	0.495	0.517

ACKNOWLEDGMENTS

This work was performed under the framework of the NICE program supported by BPI France and Conseil Régional d'Occitanie/France.


George Panagopoulos
email: george.panagopoulos@polytechnique.edu

Fragkiskos D Malliaros
email: fragkiskos.malliaros@centralesupelec.fr

Michalis Vazirgiannis

DiffuGreedy: An Influence Maximization Algorithm based on Diffusion Cascades

Keywords: influence maximization, information spreading, large-scale network analysis

Finding a set of nodes that maximizes the spread in a network, known as the influence maximization problem, has been addressed from multiple angles throughout the literature. Traditional solutions focus on the algorithmic aspect of the problem and are based solely on static networks. However, with the emergence of several complementary data, such as the network's temporal changes and the diffusion cascades taking place over it, novel methods have been proposed with promising results. Here, we introduce a simple yet effective algorithm that combines the algorithmic methodology with the diffusion cascades. We compare it with four different prevalent influence maximization approaches, on a large scale Chinese microblogging dataset. More specifically, for comparison, we employ methods that derive the seed set using the static network, the temporal network, the diffusion cascades, and their combination. A set of diffusion cascades from the latter part of the dataset is set aside for evaluation. Our method outperforms the rest in both quality of the seed set and computational efficiency.

Introduction

Albeit the massive amount of work over this problem over the past 15 years, influence maximization (IM) remains the holy grail of social network analysis. The problem, at its core, is to find a set of nodes that would infect the largest possible part of the network, if a spreading process started from them. It is proven to be NP-hard, but a greedy algorithm [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] can get at least as close as (1-1/e) to the optimum, under the two most prevalent spreading models, the independent cascade (IC) and the linear threshold (LT). The edge weights represent the probability of influence in IC and the amount of influence in LT. Typically, IM algorithms work with uniform or degree-based edge weights. This renders their spreading estimation wildly divergent from the actual spreading [START_REF] Goyal | A data-based approach to social influence maximization[END_REF], due to the complexity and diversity that governs spreading processes [START_REF] Vespignani | Modelling dynamical processes in complex socio-technical systems[END_REF]. To this end, some methods focus on learning the transmission probabilities between nodes using real diffusion cascades [START_REF] Saito | Prediction of information diffusion probabilities for independent cascade model[END_REF]. This research branch is divided into models that use the cascades to define an inferred network [START_REF] Rodriguez | Uncovering the temporal dynamics of diffusion networks[END_REF] or to adjust the edge weights of an existing underlying network [START_REF] Goyal | Learning influence probabilities in social networks[END_REF]. An example of the former is to infer a transmission probability between two news blogs based on how often and fast one copies the other, while an example of the latter is defining the strength of a follow relationship in twitter based on how many times one node retweeted the other. IM algorithms can then run on such inferred or weighted [START_REF] Goyal | A data-based approach to social influence maximization[END_REF] networks to derive the seed set. Although these methods tend to approximate real spreading better, they suffer from issues of scalability and overfitting.

In this work, we propose DiffuGreedy, an algorithm based on SimuGreedy [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] that utilizes the real diffusion cascades instead of simulations over the network. Particularly, it follows the same hill climbing manner to construct the seed set iteratively, but the computation of the marginal gain is based on a candidate seed's most suitable diffusion cascade. This function is submodular, which allows us to retain the theoretical guarantees. To showcase the effectiveness of our method, we employ the temporal Sina Weibo follower network (1.7m nodes, 400m edges), that spans 32 days and is accompanied with the retweet cascades of that time span. We keep the diffusion cascades and the network of the first 25 days as the train set and the last week as the test set. We use four different IM approaches in the train set for comparison with DiffuGreedy. The first is ranking the nodes by k-core decomposition on the follower network, which has indicated strong correlations with influence [START_REF] Malliaros | Locating influential nodes in complex networks[END_REF]. Secondly, we employ IMM [START_REF] Tang | Influence maximization in near-linear time: A martingale approach[END_REF], one of the fastest IM algorithms, to extract a seed set efficiently from the follower network as is formed at the end of the training set. The third approach utilizes NetRate [START_REF] Rodriguez | Uncovering the temporal dynamics of diffusion networks[END_REF] to infer a network from the diffusion cascades in the train set, and applies PMIA [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF] to perform IM on it. In the final method, we use the diffusion cascades to weigh the follow edges proportionally to the nodes' activity and apply SimPath [START_REF] Goyal | Simpath: An efficient algorithm for influence maximization under the linear threshold model[END_REF] on the resulting network.

It should be noted that a comparison between all these approaches has not been attempted in the literature before, to the best of our knowledge. This can be due to the lack of a common realistic evaluation methodology. Methods that work on static networks are evaluated based on their computational time and the estimated influence spread. On the other hand, diffusion learning methods are evaluated based on the behavior of the chosen seed set in unseen cascades. We deem the latter more realistic, and we choose to validate our seed set using the number of distinct nodes influenced by it in the test set [START_REF] Du | Scalable influence estimation in continuous-time diffusion networks[END_REF]. The results indicate that Diffusion Greedy and its CELF counterpart clearly outperform the rest in terms of the seed set's influence spread in the test set. In addition, the CELF approach is an order of magnitude faster to the second fastest method. Finally, we notice that the methods based on k-core and NetRate perform adequately, unlike the IMM. The paper is organized as follows. Section 2 is a brief literature review on influence maximization. Section 3 delineates some state of the art influence maximization methods we employed for our comparative analysis. Section 4 describes the new algorithm we propose. Section 5 presents the dataset and the results of our experiments, along with insights and justifications. The paper concludes in Section 6 with a contribution synopsis and suggestions for future work.

Related Work

The basis of most IM algorithms is SimuGreedy [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. Starting with an empty seed set, the algorithm adds in the set the node that provides the best marginal gain i.e. the increase of the set's influence spread, in each iteration. Due to the monotonicity and submodularity of the influence spread function under the two diffusion models, the algorithm is guaranteed to reach a near optimal solution. The most time-consuming part of SimuGreedy is the influence spread estimation, which has proven to be P-hard [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF]. Since the diffusion models are stochastic, all possible paths of influence need to be taken into account proportionally to their probability, which is not feasible, thus Monte Carlo simulations are employed. Most attempts to improve the algorithm focus on that part. CELF [START_REF] Leskovec | Cost-effective outbreak detection in networks[END_REF] capitalizes on the submodularity of a node's marginal gain, which can only diminish as the seed set grows. This means that if a candidate seed's marginal gain is higher then what the rest candidates had in the previous iteration, it is higher at the current iteration as well, hence removing the need to recompute the marginal gain of all candidates. PMIA [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF] is a heuristic approach developed for the IC model, and it is based on the maximum influence in and out arborescence (MIIA and MIOA) of every node. This is the union of all maximum influence paths that end up or start from that node. The key part of the algorithm is that paths with probability under a certain threshold are removed, assuming that influence is mostly local. SimPath [START_REF] Goyal | Simpath: An efficient algorithm for influence maximization under the linear threshold model[END_REF] is also based on the path-pruning idea, but for the LT, computing the influence spread of a node by summing the probabilities of paths that start from it. Although providing a substantial speedup, those heuristic methods do not retain theoretical guarantees, in contrast to sketch-based algorithms. The idea of sketch-based approaches is to create several instances of the network that represent varying outcomes of the edge probabilities beforehand and use them to estimate influence spread of a seed set. SKIM is an example of sketch-based IM [START_REF] Cohen | Sketch-based influence maximization and computation: Scaling up with guarantees[END_REF], which alleviates the need for Monte Carlo simulations, achieving extreme acceleration with (1 -1 e -) approximate guarantees, where is a trade-off between accuracy and efficiency. An alternative and faster sketch based methodology with the same theoretical guarantees is based on Reverse Reachable (RR) sets [START_REF] Tang | Influence maximization: Near-optimal time complexity meets practical efficiency[END_REF]. An RR set of a node consists of other nodes that can influence it. After generating a sufficient number of RR sets for random nodes, the optimum seed set can be derived by selecting the nodes that cover their majority. The intuition is that the frequency of a node's appearance in the RR sets is analogous to its influence.

While the previous algorithms work with a static network, there's a growing literature dedicated to IM based on diffusion cascades. A diffusion cascade is a series of events that takes place over the network and indicates how information spreads in it, e.g. a tweet and its list of retweets. The first model that utilized real diffusion cascades for IM, attempted to learn the transmission probabilities between nodes in IC [START_REF] Saito | Prediction of information diffusion probabilities for independent cascade model[END_REF]. The model uses survival analysis to express the probability of a node getting influenced in the course of a cascade, and it is solved using an EM algorithm. The same group proposed learning an extension of IC in continuous time (CTIC) [START_REF] Saito | Learning continuous-time information diffusion model for social behavioral data analysis[END_REF]. CTIC extends traditional IC, by defining the diffusion probability between two nodes analogous to the number of times one node was influenced by the other, as well as the time it took for the latter to get influenced by the former. The intuition behind this is that the longer it takes for a node to copy an action the less likely it is to copy it. NetRate [START_REF] Rodriguez | Uncovering the temporal dynamics of diffusion networks[END_REF] is a seminal algorithm that steps on both aforementioned works. It is based on similar modeling as [START_REF] Saito | Prediction of information diffusion probabilities for independent cascade model[END_REF], but it learns the transmission delays between nodes. NetRate can be used to infer how the nodes of the cascades are connected when the underlying network is not available. Subsequently, time-constrained IM can run on that inferred network, to give an estimate of the most influential users [START_REF] Rodriguez | Influence maximization in continuous time diffusion networks[END_REF][START_REF] Du | Scalable influence estimation in continuous-time diffusion networks[END_REF], solely based on the cascades. A similar line of work, but with a different purpose, is diffusion cascade learning [START_REF] Bourigault | Representation learning for information diffusion through social networks: an embedded cascade model[END_REF]. These machine learning models use cascades to predict whether a node will get infected or not [START_REF] Qiu | Deepinf: Modeling influence locality in large social networks[END_REF], or the size of the cascade [START_REF] Li | Deepcas: An end-to-end predictor of information cascades[END_REF] when a cascade has already started. In the intersection of the two aforementioned approaches, lie methods that use both, the follower network and the diffusion cascades. A characteristic example is the credit distribution model [START_REF] Goyal | A data-based approach to social influence maximization[END_REF]. Whenever a node u copies a node v in the diffusion cascades, credits are given to v and to the nodes that v copied. The influence spread of a seed set is the total influence credit of its seeds and is estimated efficiently, by alternating between credit estimations from the action logs and CELF. A simpler approach is to weigh the edges of the graph analogously to the activity of the nodes, e.g. how many times v has copied u in the cascades [START_REF] Goyal | Learning influence probabilities in social networks[END_REF]. Subsequently, an IM algorithm can run on this weighted network.

All aforementioned approaches, though differing methodologically, address the same problem. However, their evaluation methods are quite deviant. IM algorithms on static networks are evaluated based on their estimated spreading and time efficiency. These methods totally overlook the real spreading dynamics of the network, as they focus on the problem from a more algorithmic than data-driven perspective. In some cases, epidemic simulations like SIR and SIS are utilized to give an estimate of a seed set's spreading in the network [START_REF] Malliaros | Locating influential nodes in complex networks[END_REF]. However, these models suffer from oversimplifying assumptions [START_REF] Pei | Theories for influencer identification in complex networks[END_REF] and overlook several important characteristics of real diffusion cascades [START_REF] Gallos | Scaling of degree correlations and its influence on diffusion in scale-free networks[END_REF]. Moreover, their spreading estimate has proved inaccurate compared to actual diffusions that take place over the network [START_REF] Rossi | Exploring network centralities in spreading processes[END_REF]. Hence, although epidemic models might be a valid choice in the absence of diffusion data, in our case, we can form a more realistic ground truth based on the diffusions. Even in this case, however, evaluation is not straightforward. An erroneous example is representing the spread of a seed set in the test set by the sum of the average size of each seed's test cascades [START_REF] Xie | Dynadiffuse: A dynamic diffusion model for continuous time constrained influence maximization[END_REF]. This is inherently problematic because large cascades from individual seeds do not guarantee a large combined spread. A similar fault occurs when evaluating a seed set based on each individual seed's follows, mentions, retweets, and tweets [START_REF] Jendoubi | Two evidential data based models for influence maximization in twitter[END_REF].

Instead, our evaluation tactic is based on the number of distinct nodes influenced in the test set, by the seed set [START_REF] Du | Scalable influence estimation in continuous-time diffusion networks[END_REF]. Although not devoid of assumptions, it is the closest and most objective measure of a seed set's influence over a network at a given time span.

Influence Maximization Analysis

In this section, we describe the analytical framework we followed to apply different approaches of IM on the same dataset, which is comprised of a temporal network and diffusion cascades. As mentioned above, we split the dataset in the train and test set. The train set corresponds to the diffusion cascades and the follow relationships that took place during the first 25 days, as well as the initial follower graph which is formed before the first day of crawling. The test set consists of the last week's diffusion cascades. In the train set, we utilize four different IM techniques to derive seed sets for comparison with the seed set derived by the proposed DiffuGreedy (described in Sec. 4). A general overview of the methodology can be seen in Figure 1. Below we analyze each technique and how we applied it.

Ranking by K-core decomposition

K-core decomposition has proven a strong reliable predictor of influence in previous studies [START_REF] Kitsak | Identification of influential spreaders in complex networks[END_REF][START_REF] Malliaros | Locating influential nodes in complex networks[END_REF]. The K-core of a network is the maximal subgraph such that each vertex has at least K degree. As a proxy for IM, we can rank the nodes based on the maximum K-core they belong to, i.e. their coreness, and take the top as a seed set.

Influence Maximization via Martingales

As a representative to classic IM approaches, we use IMM, an algorithm based on the aforementioned RR sets, to derive the seed set from the follower network. This is a network of more than 95 million edges, so efficiency is of utmost importance. The most important advantage of IMM is that, in contrast with the rest of RR -based algorithms, it derives RR sets that depend on one another. As a result, the number of RR sets is diminished dramatically. In addition, it achieves a theoretical guarantee of ((1 -1/e)/(1 + ) 2 ) using martingale analysis. The network is weighted using weighted cascade [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] and the parameter , which governs the trade-off between speed and accuracy, is set to 0.1.

PMIA on the NetRate network

To perform IM based exclusively on the diffusion cascades, we employ NetRate [START_REF] Rodriguez | Uncovering the temporal dynamics of diffusion networks[END_REF] to infer the transmission rates between users in the train set. This can, in turn, define a new network with edge weights proportional to the inferred rates. The size of the inferred network needs to be very limited to satisfy the computational demands of NetRate. Hence we follow the literature [START_REF] Xie | Dynadiffuse: A dynamic diffusion model for continuous time constrained influence maximization[END_REF] and filter the cascades to keep only the most important nodes. In our experiments, degree proved to produce the most effective diffusion network. We filter all the cascades to remove nodes, either starting or participating in the cascade, that do not belong to the top 3000 nodes. Having computed the network and its transmission rates, we tried to use InfluMax, which is the archetype algorithm for continuous-time IM. However, NetRate's inferred transmission rates that exceeded 10 -6 were a mere 50 out of the 37937 inferred edges. Instead, we used PMIA [START_REF] Chen | Scalable influence maximization for prevalent viral marketing in large-scale social networks[END_REF] on the diffusion network with weights defined by weighted cascade and pruning parameter θ = 1/320. Although inferior to InfluMax, it has served as a method of comparison [START_REF] Rodriguez | Influence maximization in continuous time diffusion networks[END_REF] and provides a more then descent approximation to SimuGreedy. Moreover, PMIA is based on IC, which is closer to NetRate's continuous-time IC then LT. Finally, since the diffusion network is small the computational requirements were minuscule.

SimPath on the DataBased weighted network

To combine the information of the temporal network with the diffusion cascades, we employed an edge weighting technique [START_REF] Goyal | Learning influence probabilities in social networks[END_REF], which belongs to the DataBased approaches [START_REF] Goyal | A data-based approach to social influence maximization[END_REF]. We assume that a node u copies a node v, whenever u appears after v in a diffusion cascade and the time that u started following v is before the cascade's initiation. The edge weight is defined as:

E v,u = A v2u A v × e -Dtv,u δ , (1)
where A v2u is the number of times u copied v, A v is the total number of tweets and retweets of v, and Dt v,u is the average time that takes for u to copy v.

The first term captures the relationship's strength while the second is analogous to its speed and depicts the exponential decay of influence in time [START_REF] Saito | Learning continuous-time information diffusion model for social behavioral data analysis[END_REF][START_REF] Goyal | Learning influence probabilities in social networks[END_REF]. The parameter δ facilitates containing the second term over 0 and is set empirically to 1000. The resulting network is in the scale of 1 million edges, because their overwhelming majority had zero weight. We perform IM using SimPath with pruning parameter η = 0.01 .

The DiffuGreedy Algorithm

In this section, we propose a new influence maximization algorithm that utilizes the diffusion cascades in the train set to extract a seed set. The basic idea is to use the standard SimuGreedy algorithm [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF], but substitute the candidate seed's influence spread estimation, with a summary of the seed's diffusion cascades. The algorithm can iteratively build an influence spread network, using the most suitable seed in each iteration and its final size represents the cumulative influence spread of the seed set. The main difference with SimuGreedy lies in the calculation of a seed's influence spread. In the original algorithm, it is computed using Monte Carlo simulations of a diffusion process that starts from that seed. In our case, we substitute this with an estimate from the list of diffusion cascades that the node has initiated in the train set, for brevity's sake the node's train cascades. We define a node's influence spread as the node's train cascade that provides the highest marginal gain. Initially we experimented by using the train cascade with the median marginal gain,as a more objective estimate, or the number of distinct nodes in the node's train cascades. These approaches performed worse in our experiments, hence we kept the definition based on the cascade with the highest marginal gain. If our definition of influence spread is submodular, we can retain the (1 -1/e) theoretical guarantee [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. Below we provide the proof of submodularity and the algorithm.

Theorem 1. Computing the influence spread of a candidate seed using the diffusion cascade that maximizes the set's marginal gain, is a submodular function.

Proof. The influence spread of a node u at step t is represented by its train diffusion cascade with the highest marginal gain at that step, c t u . If another node v is added to the seed set at step t, the influence spread of c t u at t + 1 can only be diminished, due to overlaps with v's influence spread. If c t u has a high overlap with v, then another one of u's cascades will be used, let c t+1 u , in order to maximize marginal gain at step t + 1. Since we always choose the cascade with the maximal marginal gain, c t u had larger marginal gain than c t+1 u at step t. In addition, by definition, a cascade's marginal gain can only diminish or stay the same as the seed set grows. Thus, c t+1 u at t + 1 will always have smaller marginal gain then what c t u had at t, whether it is the same cascade or not, which is to be shown.

The complexity of DiffuGreedy is O(KV C), where K is the size of the seed set, V is the number of nodes that initiated a cascade and C is the average size of cascades. Since the marginal gain estimation is submodular, we can utilize CELF, which does not change the worst case complexity, but has proven to accelerate greedy [START_REF] Leskovec | Cost-effective outbreak detection in networks[END_REF]. We do not add the Diffusion CELF here due to space limitations, but its derivation is similar to the way CELF is derived from SimuGreedy [START_REF] Leskovec | Cost-effective outbreak detection in networks[END_REF]. It should be noted here, that although SimuGreedy and CELF estimate the same marginal gains, the final seed set may differ, because of multiple nodes having the same gain and each algorithm choosing based on different seed orders. This results in Diffusion CELF having a slightly inferior performance in our experiments.

Experiments

Data

We apply our methodology in the Sina Weibo dataset [START_REF] Zhang | Social influence locality for modeling retweeting behaviors[END_REF], a network consisting of more than 1.7 million nodes and 0.4 billion edges, accompanied by a set of 300,000 retweet cascades. The actual expanding follower network is given for a time span of 32 days (2012.9.28 to 2012.10.29), throughout which, almost 10 million new follow relationships occurred. The diffusion cascades are gathered by the most popular of the past 1,000 tweets of each node in the network, and they date back since the year 2009. Since our methodology relies on the intersection of the follower network and the retweet cascades, we cannot utilize the cascades before 2012.9.28, as we do not know the structure of the follower network at that time. Concurrently, we can not use the nodes in the network that are not present in the retweet cascades, because we have no information about their interactions. We thus extract the diffusion cascades of those 32 days and remove nodes from the network that are not present in these cascades. That results in a network of 641,575 nodes, with 95,272,167 edges and 18,652 cascades. We split the cascades into training [START_REF] Li | Deepcas: An end-to-end predictor of information cascades[END_REF]555) and testing (4,097).

Results

As mentioned above, our evaluation method is based on the number of distinct nodes influenced (DNI) by the seed set in the test set. We consider influenced, every node that participates in a test set diffusion initiated from one of the predicted seeds. Since we measure the size of the distinct set, potential overlaps between diffusions of different seeds are taken into account. The DNI of each method are shown in Figure 2 and Table 1 shows the average DNI of each method throughout all seed set sizes. DiffuGreedy and DiffuCELF clearly outperform the other approaches by a considerable gap. In addition, DiffuCELF takes only 16 seconds, which is almost 40 times faster then k-core decomposition, and 1000 times faster then DiffuGreedy.

One important observation is the failure of the algorithmic IM approach. Only 15 out of the 100 seeds selected by IMM had started at least one cascade in the test set, and their spread was scant. This can be attributed to a lot of follow relationships not translating into retweets, a well-known phenomenon [START_REF] Cha | Measuring user influence in twitter: The million follower fallacy[END_REF] plays a vital role in social influence analysis. Regarding SimPath in the databased weighted network, its failure might stem from the data. More specifically, we observed that the follower networks of retweet cascades are extremely sparse i.e. the ratio between the number of edges and nodes is 0.84. This happens because during crawling, 100 users were chosen at random and their follower ego-network were crawled up to three hops. Subsequently, last 1000 tweets of each user are retreived, each one containing a list of retweets. This list of retweets is filtered to contain only nodes that are in the crawled set. However, the follow relationships indicating how the tweet reached a node can be lost and as a result, the cascades are comprised of mostly unconnected nodes. Therefore, the DataBased weighing results in very few retained edges. Finally, the lack of success of the diffusion network approach could be attributed to the substantial mismatch with the actual follower network. Less than 1% of the inferred edges were actual follow edges. Even though as mentioned above, there were a lot of follow relationships in the diffusion cascades missing, it is safe to assume that a large part of the diffusion network was not based on direct follow edges, but rather on higher order relationships. These relationships although useful, are not as stable as direct ones i.e. an active follower is more likely to retweet than a follower's active follower. The retweets in the test set might consist of mostly followers, which caused this approach's deficiency. The code, along with instructions to reproduce the experiments can be found on github4 .

Conclusion

As network science drifts towards data-driven approaches and increasingly more networks are accompanied by diffusion cascades, we have to reconsider our view of many important problems. In this study, we address influence maximization on a large scale social network. We employ multiple state-of-the-art methods, each exploiting a different aspect of the dataset, and propose an algorithm that outperforms them. In addition, we utilize an evaluation methodology based on actual diffusion cascades, as a more realistic alternative to epidemic simulation models. For future work, we plan to examine methods based on machine learning to derive the seed set. More specifically, while numerous neural network algorithms have been developed recently for influence or outbreak prediction [START_REF] Qiu | Deepinf: Modeling influence locality in large social networks[END_REF][START_REF] Li | Deepcas: An end-to-end predictor of information cascades[END_REF], the problem of influence maximization remains unaddressed. This is a promising path that we would like to explore further in subsequent steps.

Fig. 1 .

 1 Fig. 1. An overview of the models we employed and which data they utilize. The upper quadrants correspond to diffusion cascades and the lower to the follow relationships established in time. The left quadrants belong to the train set and the right to the test set. Each network represents a different type of data. The static follower network is formed at the last day of the training set, so it is under the vertical axis. Each rectangle represents a different method, and its position indicates which type of data it is based on.

Fig. 2 .

 2 Fig. 2. Number of distinct nodes influenced (DNI) in the test set by the seed set of each method. Method labels are ordered based on their average DNI.

  Algorithm 1 Find the seed's cascade with maximum marginal gain

		procedure MarginalGain(f inal spread,seed cascades)
	2:	set max gain ← -1, casc idx ← -1
		for casc ← 0; casc < size(seed cascades); casc + + do
	4:	marginal gain ← size(f inal spread ∪ seed cascades[casc]))
		if marginal gain > max gain then
	6:	max gain ← marginal gain
		casc idx ← casc
	8:	return max gain, casc idx
	Algorithm 2 Influence maximization using nodes' diffusion cascades
		procedure DiffuGreedy(node cascades,seed set size)
	2: seed sed ← [], f inal spread ← ∅
		while size(seed set) < seed set size do
	4:	set max seed = -1, max gain = 0, max cascade = -1
		for seed = 0; seed < size(node cascades); seed + + do
	6:	marginal gain, cascade idx = MarginalGain(final spread,node cascades[seed])
		if marginal gain > max gain then
	8:	max gain ← marginal gain
		max seed ← seed
	10:	max cascade ← cascade idx
		f inal spread ← f inal spread ∪ node cascades[max seed][max cascade])
	12:	seed sed.insert(max seed)
		delete node cascades[max seed]
	14:	return size(inf luence spread)

Table 1 .

 1 Average evaluation metrics and computational time for each method. Preprocessing took 999, NetRate 26398 and PMIA 569 b Extraction and weighing took 103898 and IMM 180 c Extraction took 2981, weighing 93898 and SimPath 29

	Method	DNI	Computational Time (sec)
	DiffuGreedy DiffuCELF	52,600 42,325	16,504 16
	K-cores	31,657	632
	NetRate PMIA	21,863	27,966 a
	IMM	1,248	104,078 b
	DataBased SimPath	56	96,908 c
	a

https://github.com/GiorgosPanagopoulos/DiffuGreedy-Influence-Maximization