text:
# Magnetic Materials

The introduction of material media into the study of magnetism has very different consequences as compared to the introduction of material media into the study of electrostatics. When we dealt with dielectric materials in electrostatics, their effect was always to reduce  below what it would otherwise be, for a given amount of free electric charge. In contrast, when we deal with magnetic materials, their effect can be one of the following:
1. To reduce  below what it would otherwise be, for the same amount of free electric current (diamagnetic materials)
2. To increase  a little above what it would otherwise be (paramagnetic materials)
3. To increase  a lot above what it would otherwise be (ferromagnetic materials)

# Magnetisation, or Magnetic Polarisation

Magnetisation is the property of some magnetic materials which describes a magnetic field created by those materials themselves and the effects of some external magnetic field on those materials.

Magnetisation  is defined as the amount of magnetic moment per unit volume. It is expressed in amperes per metre (A/m).

The origin of the magnetic moments that create the magnetisation can be microscopic electric currents (bound current, Ib) due to
• either the rotation of electrons around the positive nucleus, or
• the spin of the electrons
Both of these electronic motions produce internal magnetic fields  that are similar to the magnetic field produced by a current loop. The equivalent current loop has the magnetic moment,

where S is the area of the loop and Ib is the bound current.

# Magnetisation in Maxwellâ€™s Equations

Magnetic Susceptibility (χm)

The magnetic susceptibility χm of a magnetic material is a measure of the degree of magnetisation of a material in response to an applied magnetic field.

Permeability

Permeability (Î¼) is the degree of magnetisation of a material that responds linearly to an applied magnetic field.

# Classification of Magnetic Materials

Depending upon the values of the magnetic susceptibility (χm) or the relative permeability (Î¼r), magnetic materials are broadly classified into three groups as

1. Paramagnetism
2. Diamagnetism
3. Ferromagnetism
1. Paramagnetism
The atoms or molecules comprising paramagnetic materials have a permanent magnetic dipole moment. In the absence of any applied external magnetic field, the permanent magnetic dipoles in a paramagnetic material are randomly aligned and thus do not have any magnetisation  and thus, the average magnetic field  is also zero.

However, when we place a paramagnetic material in an external field , the dipoles experience a torque that tends to align  with , thereby producing a net magnetisation  parallel to . Since  is parallel to , it will tend to enhance the field. Hence, for paramagnetic materials, magnetic permeability, Î¼ > Î¼0.

In most paramagnetic substances, the magnetisation  is not only in the same direction as , but also linearly proportional to it. This is possible because without the external field there would be no alignment of dipoles and hence no magnetisation.

The linear relation between  and  is expressed as,

where χm is a dimensionless quantity called the magnetic susceptibility.

Thus, the net magnetic field can be written as,

where Î¼r = (1 + χm) is called the relative permeability of the material.

For paramagnetic materials, Î¼r > 1 or magnetic susceptibility, χm > 0 (positive), although χm is usually of the order of 10-6 to 10-3. Paramagnetism is temperature dependent.

Examples of Paramagnetic Materials are air, platinum, tungsten, potassium, aluminium, chromium, palladium, copper sulphate, manganese, etc.
1. Diamagnetism
In the case of diamagnetic materials, the magnetic fields due to electronic motions completely cancel each other and thus, the magnetic material does not have permanent magnetic dipoles. The presence of an external field  will induce magnetic dipole moments in the atoms or molecules. However, these induced magnetic dipoles are antiparallel to , leading to a magnetisation  and average field antiparallel to and therefore a reduction in the total magnetic field strength. Hence, for diamagnetic materials, magnetic permeability, Î¼ < Î¼0.

For diamagnetic materials, relative permeability, Î¼r<1, or magnetic susceptibility, χm < 0 (negative), although χm is usually of the order of -10-5 to -10-9.

Examples of Diamagnetic Materials are copper (χm = -0.95 Ã— 10-5), gold (χm = -3.2 Ã— 10-5), silver (χm = -2.6 Ã— 10-5), lead, silicon, diamond, bismuth (χm = -16.6 Ã— 10-5), antimony, mercury, tin, zinc, alcohol, hydrogen, nitrogen, water, etc.
1. Ferromagnetism
In ferromagnetic materials, there is a strong interaction between neighbouring atomic dipole moments. Ferromagnetic materials are made up of small patches called magnetic domains, as illustrated in Fig. An externally applied field  will tend to line up those magnetic dipoles parallel to the external field, as shown in Fig. The strong interaction between neighbouring atomic dipole moments causes a much stronger alignment of the magnetic dipoles than in paramagnetic materials.

Examples of Ferromagnetic Materials are iron, steel, nickel, cobalt.

# Hysteresis in Ferromagnetic Materials

The permeability Î¼ of a ferromagnetic material is not a constant, since neither the total field nor the magnetisation  increases linearly with . Although the relation  is applicable for all types of magnetic materials, the relation between  and  for ferromagnetic materials is not unique, but is dependent on the previous magnetic history of the material. The phenomenon is known as hysteresis. The variation of  as a function of the externally applied field  is shown in Fig. The curve is known as a hysteresis curve or magnetisation curve or Bâ€“H curve.

Hysteresis curve or magnetisation (B-H) curve

From the hysteresis loop, a number of primary magnetic properties of a material can be determined.
1. Retentivity

(The value of  at the point b on the hysteresis curve) It is a measure of the residual magnetic flux density corresponding to the saturation induction of a magnetic material. In other words, it is the ability of a material to retain a certain amount of residual magnetic field when the magnetising force is removed after achieving saturation.
2. Residual Magnetism or Residual Flux

It is the magnetic flux density that remains in a material when the magnetising force is zero. The residual magnetism and retentivity are the same when the material has been magnetised to the saturation point. However, the level of residual magnetism may be lower than the retentivity value when the magnetising force did not reach the saturation level.
3. Coercive Force

(The value of  at point c on the hysteresis curve.) This is the amount of reverse magnetic field which must be applied to a magnetic material to make the magnetic flux return to zero.
4. Hysteresis Loss

The area of a hysteresis loop gives the energy loss per unit volume during one complete cycle of periodic magnetisation of a ferromagnetic material. This is called hysteresis loss. This loss is in the form of heat.
5. Permeability

As has been previously mentioned, permeability is a material property that describes the ease with which a magnetic flux is established in a material. It is the ratio of the flux density to the magnetising force and is represented by the equation .
This equation describes the slope of the curve at any point on the hysteresis loop. The permeability value given in papers and reference materials is usually the maximum permeability or the maximum relative permeability. The maximum permeability is the point where the slope of the Bâ€“H curve for the unmagnetised material is the greatest. This point is often taken as the point where a straight line from the origin is tangent to the Bâ€“H curve as shown in Fig.

â€‹
Determination of permeability from hysteresis curve

The relative permeability is arrived at by taking the ratio of the materialâ€™s permeability to the permeability in free space (air).
1. Reluctance

It is the opposition that a ferromagnetic material shows to the establishment of a magnetic field. Reluctance is analogous to the resistance in an electrical circuit.

The shape of the hysteresis loop tells a great deal about the material being magnetised. The hysteresis curves of two different materials are shown in the graph.
â€‹Relative to other materials, a material with a wider hysteresis loop has
• Lower permeability
• Higher retentivity
• Higher coercivity
• Higher reluctance
• Higher residual magnetism
• Higher loss
Relative to other materials, a material with a narrower hysteresis loop has
• Higher permeability
• Lower retentivity
• Lower coercivity
• Lower reluctance
• Lower residual magnetism
• Lower loss
â€‹
Different shapes of hysteresis curves


text:
Session 77 - Binary Stars.
Display session, Wednesday, January 15
Metropolitan Ballroom,

[77.16] Doppler Tomography of Ultraviolet Spectra of the RS CVn Binary HR 1099

E. W. Rosolowsky, M. T. Richards (U. Virginia)

Archival IUE spectra of HR 1099 from 1978 -- 1994 were used to obtain reconstructed Doppler images of the sources of emission in the binary. Doppler tomograms were made from the Mg h+k, C II, He II and Ly \alpha lines. These results are consistent with chromospheric emission in the case where the gas is tidally enhanced. The tomograms show the gas centered on and around the velocity of the more magnetically active K star with a concentration at the velocity of the L1 point.

format: plain


text:
## Polyholes Revisited

Some time ago Nophead did some experiments to investigate why holes printed by reprap machines come out undersized.

I’ve also noticed this in my prints and have in some cases manually just ‘added a bit’ and re-printed the part. This isn’t very methodical so I decided to give Nopheads polyholes compensation a try. However even on paper the hole sizes suggested seem to be lower than some of the values I found by trial and error.

I decided to do a formal test and came up with the following OpenSCAD script. I have a full range of 19 drill bits from 1mm up to 10mm in 0.5mm increments.

The polyholes function is left untouched from Nopheads original and the rest just creates a nice shaped test piece.

Unfortunately the test confirmed what I suspected, and not a single drill bit fit in my test piece. In fact I had to shift all the bits up one space, the 9.5mm bit fitting into the 10mm hole and so on. For the smaller hole sizes even this didn’t work.

I decided to revisit the initial effects that Nophead outlined in his post which were:

• Faceting error
• Segment pausing
• Arc shrinkage
• Corner cutting

The faceting error comes about from CAD programs using the outer circumcircle as the basis for the radius of the polygon.

For a hole you actually need to use the smaller incircle radius. To convert from the incircle radius for a regular polygon with n sides you simply apply the following:

$R_{outer} = R_{inner} / \cos(\frac{\pi}{n})$

This formula can actually be quite useful for calculating the number of sides needed given a radius and tolerance. Simply re-arrange in terms of n to give:

$n = \pi / \cos^{-1}(\frac{r-t}{r})$

For values of r between 1mm and 20mm, and a tolerance of 0.1mm this gives values for n ranging between 7, and 23. This brings me on to segment pausing. I find it hard to believe that current reprap electronics will have significant delay when trying to produce 23 short line segments. Nophead dismissed this since his electronics were very low latency, and so will I.

The next factor is arc shrinkage. I found it quite odd that Nophead acknowledged this factor and referenced Adrian Bower’s calculations which compensate for this, but then dismisses it because the numbers come out too small. It occurred to me that Adrian’s calculations are based on a perfect circle, and so the faceting error calculations have to be used in conjunction with arc compensation.

$R_{outer} = \frac{t + \sqrt{t^2 + 4r^2}}{2} / \cos(\frac{\pi}{n})$

The value for t in this equation needs to be the track width of the extruded path. I wanted to use Slic3r’s formula for this which assumes the area of a track is the same as area of the filament at the nozzle, and that the shape of the track is a rectangle with two semicircles for the sides:

The area at the nozzle is just the area formula for a circle where d is the nozzle diameter:

$A_{nozzle} = \frac{\pi d^2}{4}$

The area of the track is just the sum of a circle area and rectangular area where h is the layer height (which is also the semicircle diameter):

$A_{track} = (x \times h) + \frac{\pi h^2}{4}$

Solving for x when both areas are the same gives:

$x = -\frac{\pi(h^2-d^2)}{4 h}$

The total track width then is x plus the width of the two semicircles:

$w = x + h$

Which gives:

$w = h -\frac{\pi (h^2-d^2)}{4 h}$

Putting this all together I created this new OpenSCAD script:

Here are the results:

Every drill bit fit snugly in the hole it was meant for. Even the small sizes worked surprisingly going down to a 1mm drill bit. But wait… I haven’t accounted for corner cutting. Well this is the aspect where I think I am going to have to disagree with Nophead. Not least because I didn’t account for it in my test above, but also because the assumption is that the filament is being stretched as it goes round corners, and this seems wrong to me. Surely the filament should be being extruded at a rate equal to the motion of the nozzle so that no stretching should occur. In fact in contrary to this Slic3r utilises a faster motion than the extrude rate to deliberately stretch the filament for making bridges, but not during normal perimeter generation. Its odd because Nophead says this is this is the dominant effect on his machines, and is the main justification for using less facets for the holes. Perhaps his extrusion rate is lower and so the filament does get stretched.

For holes below 2mm in diameter Nophead’s formula says you need 4, or 3 facets, which are not really holes at all. I would argue that smaller holes require a higher tolerance to produce accurate results, and from the formula for n above that means you need more facets, not less.

You can really notice the how the difference in facets effects the quality of the holes in the two test pieces:

As a final note I thought its worth mentioning that even a machined hole will be considered an interference fit (tight) if its drilled at the same diameter as the shaft or bolt that its intended for. For this reason a table of clearance holes is used

 Size Pitch (mm) Tapping Diameter (mm) Clearance Holes (mm) Coarse Fine Coarse Fine Close Medium Coarse M1.6 0.35 1.25 1.7 1.8 2.0 M2 0.4 1.6 2.2 2.4 2.6 M2.5 0.45 2.05 2.7 2.9 3.1 M3 0.5 2.5 3.2 3.4 3.6 M4 0.7 3.3 4.3 4.5 4.8 M5 0.8 4.2 5.3 5.5 5.8 M6 1.0 5.0 6.4 6.6 7.0 M8 1.25 1.0 6.8 7.0 8.4 9.0 10.0 M10 1.5 1.25 8.5 8.7 10.5 11.0 12.0 M12 1.75 1.25 10.2 10.8 13 14 15 M16 2.0 1.5 14.0 14.5 17.0 18.0 19.0 M20 2.5 1.5 17.5 18.5 21.0 22.0 24.0 M24 3.0 2.0 21.0 22.0 25.0 26.0 28.0 M30 3.5 2.0 26.5 28.0 31.0 33.0 35.0 M36 4.0 3.0 32.0 33.0 37.0 39.0 42.0


text:
# What is the energy of a superposition of energy eigenstates?

Suppose I have a system say SHO in a superposition of energy eigenstates $$|{n_1}\rangle$$ and $$|{n_2}\rangle$$ given by $$|{\psi}\rangle = \frac{1}{\sqrt{2}}|{n_1}\rangle + \frac{1}{\sqrt{2}}|{n_2}\rangle$$.

If I measure the energy of system there is equal probability of getting $$(n_1 + \frac{1}{2})\hbar\omega$$ or $$(n_2 + \frac{1}{2})\hbar\omega$$.

The question then arises where does rest of the energy go or come from? On one good day I measure system to be in state $$|{n_1}\rangle$$ while on other I measure it to be $$|{n_2}\rangle$$. It seems to me that it violates the energy conservation. Does this have to do with the measuring device? If yes then why do we never talk about it in formulating states?

• Note that after you measure and get one energy or the other, the state collapses and now has that definite energy. I think you should be asking the general question of what the energy of a superposition is. – Ryan Unger Feb 9 '15 at 14:48
• Yea that is precisely my question! The system could have collapsed in any one of the energy states. Then how come does it have exactly the energy corresp. to that state. Also by energy conservation one could say that the system had precisely that much energy to begin with i.e it was never in the other state. – Physicsaholic Feb 9 '15 at 15:26

First, the energy expectation value of the superposition state you have written down is

$$\left(\frac{n_1 + n_2}{2} + \frac{1}{2}\right)\hbar\omega$$

and one might naively conclude that therefore the energy of the state lies in between the energy of its constituents.

This naive concept doesn't work, though - the "energy" of a state that is not an energy eigenstate is not well-defined, just as the spin of a state that is not a spin eigenstate is not well-defined - all you have is the expectation value, which tells you what you would get averaging over many measurements. The spin superposition $$|{\uparrow}\rangle + |{\downarrow}\rangle$$ hasn't got a definite spin, and it is certainly not zero, although its expectation value is.

Therefore, the question "Where does the energy come from/go?" is simply ill-posed. A state that is not an eigenstate has no well-defined property "energy".

You might ask how conservation of energy is realised here, and the answer is simple and unsatisfactory at first: Classical conservation laws are realized on the quantum level as operator laws, or, in this case, as the conservation of energy expectation value

$$\frac{\mathrm{d}}{\mathrm{d}t}\langle \psi \vert H |{\psi}\rangle = 0$$

in the course of the usual time evolution, which, by Ehrenfest's theorem, is always true for time-independent Hamiltonians. Thus, energy is indeed conserved.

The measurement process itself constitutes an interaction with the state $$\psi$$, and is in particular not a unitary (time) evolution on the system of the state. There is hence no reason to demand that the energy expectation of a state after measurement be the same as before.

If energy is conserved, how so that a measurement of the energy of a state, such as $$\psi = N (\phi_1 + \phi_2),$$ could result in two different energies? I think your question is easiest to tackle with the consistent histories interpretation of QM (though you'll reach similar conclusions with any other interpretation).

We must remember that energy can be exchanged between between the state $\psi$, the "subsystem" that made that state, and the "subsystem" (i.e. measuring apparatus) with which you propose to measure the state.

If we consider the whole system, state, the original process, and the measuring apparatus, energy is always conserved. Each possible (consistent) history of the state conserves energy - if the state has "more" energy upon measurement, it is because the process that made that state gave it more energy (though until measurement, the history of the state is undetermined).

In general, conservation laws, such as the conservation of energy, are obeyed by consistent histories for closed systems.

• energy is not conserved because there is no fix energy in the system to be measured. – Sofia Feb 9 '15 at 16:45
• i sort of agree, though i find that misleading. i'd say that energy is conserved for every possible consistent history. – innisfree Feb 9 '15 at 16:46
• in the frame of standard QM the wave-function is whatever we know. A constant of motion is the value of that operator whose eigenvalue is our wave-function. If there is no such operator, our wave-function admits no constant of motion. Do you want examples? Coherent light. Consistent history, or Bohm interpretation, or many-worlds (there are many others) are not what the asker asked. – Sofia Feb 9 '15 at 17:02
• i'm honestly not sure what your asking/telling me? you're right, though, that the OP didn't ask for an explanation in terms of a particular interpretation, but consistent histories is useful for this kind of question. – innisfree Feb 9 '15 at 17:10
• consistent histories is an interpretation. Let me say otherwise, in the frame of the standard quantum theory did you learn of consistent histories? I don't remember this interpretation exactly, but I know that it is an interpretation. – Sofia Feb 9 '15 at 17:23

Suppose you prepare a state and you want to determine which state you have created. Of course a single measure tells you nothing unless you know a priori that you have created an eigenstate of the Hamiltonian. So from a practical point of view, a measurement is a repetition of the same experimental operations on a large enough ensemble of identical copies of the state you are creating. If you find that half of the times your state has energy $E_1$ and the other half of the times it has energy $E_2$, you can declare that the state you are producing is a superposition of state $\psi_1$ and state $\psi_2$, the coefficients of the superposition coming from the measured statistics.

Formally, the energy of this state is then the statistical averages of all the outcomes, which in this simple case is just $\frac{E_1 + E_2}2$, but in general is just the expectation value of the state on the Hamiltonian.

• Let me rephrase what I think OP's question is. Suppose we have some superposition oscillator, not an ensemble. We can get one of two energies by measuring the energy, with equal probabilities. Suppose we get the lower of the two. Where does the energy go that would have allowed it to be in the higher energy state? – Ryan Unger Feb 9 '15 at 15:37
• as I said the measurement procedure in quantum mechanics is of statistical nature. measuring something just once bears no information so it is meaningless. Hence why you need ensembles. – Phoenix87 Feb 9 '15 at 15:39
• are you saying that energy is (clearly) conserved if one considers correlation between the measured state and the "system" from which the state was produced? – innisfree Feb 9 '15 at 15:51
• i think the problem of conservation of energy in this case is even immaterial. Once you have created a state you might want to know which state you have created, therefore you measure its energy. Which other energy is there to compare this measure with? – Phoenix87 Feb 9 '15 at 15:54
• i prepare a superposition (i know my state is a superposition of energy eigenstates), then take a measurement of its energy. i can compare this energy to other energies I could have obtained from my measurement. – innisfree Feb 9 '15 at 16:01

As you write the state $|\psi\rangle$ it seems that your system is in a superposition of $n_1$ oscillators and $n_2$ oscillators, each one of energy $\hbar \omega$. So, in the state $|\psi\rangle$ the number of oscillators in not fixed, and with it the energy is not fixed, it is not a constant of motion. In this case the question where go the other oscillators is meaningless.

The situation is analogue with the 2slit experiment. The path is not a constant of motion, i.e. if you put detectors near the slits you can find in one trial that the particle passed through one slit, and in another trial you can find that is passed through the other slit.

Energy makes no exception, it may be no constant of motion as any other variable. That doesn't mean that if the measurement gave us $E_1$ before the measurement the energy was $E_1$. No, if the energy is not a constant of motion is wasn't $E_1$.


text:
Formulas no longer working on QV 11

Hi,

I am trying to load information from an excel file(.xlsx), and I have formatted some of the contents, but found the following formulas no longer working on the new QV 11.

1. Day
2. Month
3. Year
4. Isnull
5. Date

The following is my script.

b3_num,

text(mid(b3_num,7,8)) as CREFNO,

b2_submit,

date(das_date) as 'das date',

refund_amt,

cheque_dat,

cheque_num,

cancelled,

date(cancelled) as 'cancel date',

day(cancelled) as 'cancel day',

month(cancelled) as 'cancel month',

year(cancelled) as 'cancel year',

isnull(cancelled) as 'datenull',

reject_dat,

resub_date,

b3_date,

auditor,

client_ref,

expl,

justify,

submitted

FROM

[C:\Documents and Settings\shua\Desktop\mmi8-20120319B2STAT.xlsx]

(ooxml, embedded labels, table is mmi8);

but the output does not come out the way it was in QV 10.

Thanks.

Sharon

• Formulas no longer working on QV 11

Figured it out, it was because of the date format.

Thanks.

Sharon


text:
# How is an X509 certificate signer verified?

Lets say I create a self-signed X509 certificate A and use it to issue certificate B. I put certificate A in my trusted root authorities so that all certificates signed by it are accepted. My question is:

When I then use a service protected by cert B, how does my computer know it was actually signed by cert A? Is the parent certificate somehow embedded into its child?

• It's hard to comment without a sample of the output of .NET's X509Certificate class.. – ansur Oct 1 '12 at 12:34
• This question is language-agnostic. When people say 'ssl certificate' or just 'certificate' they are usually referring to an x509 certificate, en.wikipedia.org/wiki/X.509 – Despertar Oct 1 '12 at 17:18

In a X.509 certificate, the name of the issuer (in your example, A's name) is also included (as issuerDN). Also, a certificate can contain an extension which points to a place where the issuer's certificate can be downloaded (the "Authority Information Access", section 4.2.2.1 of RFC 5280); note that since all certificates are signed entities which are accepted and use only after having verified these signatures, they can be downloaded and transported with little care. Finally, it is customary, in protocols where a party can show a certificate, to actually show a list of certificates containing needed intermediate CA certificates. This is what happens, for instance, in an SSL Certificate message.

All this gives a lot of ways for a computer to do certification path building, i.e. reconstructing chains of certificate on which validation (including verifying cryptographic signatures) seems relevant.

When the CA issues the certificate, they sign it using their private key. Only the CA's public key can verify that the signature is authentic and the certificate has not been tampered with.

What is odd is that the signature property seems to be missing in a lot of instances (.NET's X509Certificate class and when viewing a certificate in Windows). I've found that even though it is not always displayed, it is still inside the certificate. Given a certificate in DER binary format, you can decode it into plain text which DOES show the signer's signature.

openssl x509 -text -noout -inform DER -in certFile.der

Signature Algorithm: sha1WithRSAEncryption
30:d9:40:ac:d8:0d:46:81:68:14:8a:c6:a7:29:96:4e:b4:58:
7b:e6:12:3f:45:4f:c6:9b:18:aa:f2:99:23:ee:48:df:5f:c0:
a3:c7:e4:ba:3a:bc:6f:58:57:fe:a8:a7:23:d0:d1:9a:47:a6:
42:1a:d8:20:e8:f1:ec:76:43:47:0b:75:d6:a1:d2:71:2b:f7:
19:96:e3:48:57:e2:36:0f:0c:25:5d:7f:f8:26:50:c2:5e:80:
22:d3:01:33:f9:4c:3b:f8:a8:39:f1:6c:41:74:de:ba:96:6a:
0b:f1:e6:f0:7b:d8:1f:42:ec:b5:73:d1:94:1b:01:4a:4c:13:
ca:5e:2b:af:fd:2c:eb:43:d3:fc:2f:ea:5a:8d:db:a9:6a:f6:
92:04:c4:97:a3:7a:52:e5:a0:b1:1b:8f:47:bb:43:a3:2c:1a:
fb:31:d9:51:7c:23:7b:57:8e:73:46:81:c4:25:f3:48:c5:a1:
8f:0d:3d:f2:e1:4b:fd:7f:49:b9:f9:b1:2a:c2:22:9e:8a:85:
61:bd:b7:18:8e:56:33:a4:6e:d2:7d:db:2e:37:d0:fb:9a:35:
87:c8:2a:69

To validate this certificate, one needs a second certificate that matches the Issuer (Thawte Server CA) of the first certificate. First, one verifies that the second certificate is of a CA kind; that is, that it can be used to issue other certificates. This is done by inspecting a value of the CA attribute in the X509v3 extension section. Then the RSA public key from the CA certificate is used to decode the signature on the first certificate to obtain a MD5 hash, which must match an actual MD5 hash computed over the rest of the certificate.

• "encrypting" the hash with the private key isn't quite right. See: security.stackexchange.com/a/20925/2435 – Bruno Oct 2 '12 at 1:33
• @Bruno Yeah I had just read that one as well. Turns out it uses a digital signature algorithm rather than encryption. I'll update that part, thanks. – Despertar Oct 2 '12 at 1:58


text:
# Well-Characterized vs NP-Complete

Definition: Well-Characterized also known as Good-Characterized is defined as follows:

Problem that have Yes and No certificates i.e., are in NP $\cap$ co-NP, are said to be Well-Characterized. (Reference: V.Vazirani, Approximation Algorithm)

Does exist any Well-Chracterized problem that is also being NP-Complete? I don't looking for any proof, I just want a real-world example of such problem.

• What do you mean by "well-characterized"? Can you give a definition? What are your thoughts? What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Feb 11 '17 at 17:45
• @D.W. Thanks for you advice, I edit my question a bit. – Amir Feb 11 '17 at 21:32
• In its current form, the question may not be very interesting, but it seems to be more interesting to ask whether there exist a well-characterized problem that is not known to be in PTime? I am not aware of any such problem and I would very much like to learn more about this. One might think that some intermediate problems such as graph isomorphism (GI) are good candidates... However, although it is known that GI is in NP, it is open whether it is in coNP. Therefore, it maybe a good idea to also add this question... – Heyheyhey Feb 12 '17 at 19:27

We don't know. If any NP-complete problem were in co-NP, then we'd have NP$\,=\,$co-NP and we don't know whether that's true or not.


text:
## Abstract

Binary undirected graphs are well established, but when these graphs are constructed, often a threshold is applied to a parameter describing the connection between two nodes. Therefore, the use of weighted graphs is more appropriate. In this work, we focus on weighted undirected graphs. This implies that we have to incorporate edge weights in the graph measures, which require generalizations of common graph metrics. After reviewing existing generalizations of the clustering coefficient and the local efficiency, we proposed new generalizations for these graph measures. To be able to compare different generalizations, a number of essential and useful properties were defined that ideally should be satisfied. We applied the generalizations to two real-world networks of different sizes. As a result, we found that not all existing generalizations satisfy all essential properties. Furthermore, we determined the best generalization for the clustering coefficient and local efficiency based on their properties and the performance when applied to two networks. We found that the best generalization of the clustering coefficient is , defined in Miyajima and Sakuragawa (2014), while the best generalization of the local efficiency is , proposed in this letter. Depending on the application and the relative importance of sensitivity and robustness to noise, other generalizations may be selected on the basis of the properties investigated in this letter.

## 1  Introduction

A complex system can be modeled as a graph or network, which is composed of nodes and edges connecting them. Analysis over a wide range of complex systems has led to a fundamental insight: many complex systems often share certain topological characteristics, and these can be captured by graph-theoretical metrics (Barabasi & Oltvai, 2004; Amaral & Ottino, 2004; Zhang & Horvath, 2005; Bullmore & Sporns, 2009; Fornito, Zalesky, & Breakspear, 2013). The small-world topology for example, has been found in many real-world networks (He, Chen, & Evans, 2007; Opsahl & Panzarasa, 2009; Batalle et al., 2012; Vandenberghe et al., 2013), and is an indication of the cost-efficiency of these networks.

While traditional graph analysis uses binary edges to enhance contrast between strong and weak connections, there is an increasing demand for using edge weight, which entails potentially important information. Incorporating edge weights in the graph analysis calls for generalizations of the graph metrics. While some of these measures can be naturally generalized to a weighted version (e.g., node degree to node strength), others cannot be generalized in a straightforward way. The generalization of clustering coefficient and local efficiency, used to quantify the small-world topology (Watts & Strogatz, 1998; Achard and Bullmore, 2007; Batalle et al., 2012), is far from trivial.

The clustering coefficient reflects the tendency that neighbors of a node are also neighbors to each other (Rubinov & Sporns, 2010). The clustering coefficient is high in small-world networks compared to random networks (Watts & Strogatz, 1998). Local efficiency is a measure for the fault tolerance of the system: it measures how efficient the communication is between neighbors of a node when that node is removed (Latora & Marchiori, 2003). A small-world network features a local efficiency intermediate to that of regular (lattice) and random network (Achard & Bullmore, 2007; Batalle et al., 2012). The two measures are related in a way that the clustering coefficient in an undirected network is found to be a reasonable approximation of local efficiency (Latora & Marchiori, 2003).

Although it is straightforward to find the neighbors of a node, the question of how to define their weighted surrogates is far from obvious. Several generalizations have been proposed (Barrat, Barthelemy, Pastor-Satorras, & Vespignani, 2004; Onnela, Saramäki, Kertész, & Kaski, 2005; Zhang & Horvath, 2005; Saramäki, Kivelä, Onnela, Kaski, & Kertesz, 2007; Opsahl & Panzarasa, 2009; Miyajima & Sakuragawa, 2014; Rubinov & Sporns, 2010). Different definitions capture slightly different aspects of the network, yet some of the generalizations are not designed for fully weighted networks (Rubinov & Sporns, 2010; Barrat et al., 2004; Onnela et al., 2005). These generalizations require the removal of the weak or noisy connections beforehand. A preferable solution is to adapt the equations in such a way that they can be used for a fully weighted network (Zhang & Horvath, 2005; Saramäki et al., 2007; Opsahl & Panzarasa, 2009; Miyajima & Sakuragawa, 2014).

In this letter, we first define a number of essential and useful properties that ideally should be satisfied when using a generalized graph measure and explain how we will evaluate them. Then we review the existing generalizations, and we propose new generalizations for the local efficiency for fully weighted undirected networks with no self-connections. Finally, we make a thorough comparison of the different generalizations and apply them to two real-world networks.

## 2  Methods

Assume an undirected weighted network with nodes and an adjancy matrix for which the th element is 1 if an edge between and exists and 0 otherwise. In this work, we assume that no self-connections are present: . For a binary undirected network, the clustering coefficient for node is given by
2.1
with the degree of node . The node degree is defined as the number of nodes connected to node . The local efficiency is defined as
2.2
in which is the subgraph consisting of the neighbors of excluding node itself, and is the length of the shortest path between nodes and containing only neighbors of . If no path containing these neighbors is found, .
In a weighted network, we define the weight matrix in which each element represents the weight between node and node . All weights are assumed to be positive. If no connection is present, the weight is 0. In this work, we focus on networks without self-connections: . The node degree is calculated based on the presence of connections with nonzero weights irrespective of the amplitude. In case of a fully connected weighted network with nodes and no self-connections, . The node strength, which takes into account the weight of the connection, is defined by
2.3
Note that for a binary network in which if a connection is present between nodes and and 0 otherwise, .

### 2.1  Properties of Generalized Graph Measures

A generalization of a binary graph measure should ideally satisfy some properties. Some of these properties are essential, while others may depend on the application. The essential properties are:

• General versatility. If the input is given as a binary network, the output of the generalizations should give the same results as the binary version: when (Miyajima & Sakuragawa, 2014).

• Continuity. The graph measure should be continuous, that is, in which except for one connection weight, which differs by (Miyajima & Sakuragawa, 2014).

• Sensitivity. The graph measure should be able to make a distinction between different cases for which the graph measure is designed. Because the clustering coefficient and the local efficiency are defined using triangles, we will evaluate the six possible cases in which the weight is either low or high in one of the connections of the triangle (see Figure 1).

• Robustness to noise. The graph measure for node should be robust when adding noise to the weights of the connections. If we assume a noise matrix , which represents additive noise on each connection weight , and define the mean relative error (in percent) with respect to the noise-free measures as
2.4
then a small value of should lead to a small error value .

Figure 1:

Six possible triangle configurations for node filled in black. Normal and dashed lines represent strong and weak edges, respectively.

Figure 1:

Six possible triangle configurations for node filled in black. Normal and dashed lines represent strong and weak edges, respectively.

Additional useful properties can be defined, but these properties depend on the application under investigation and should not be considered essential:

• Weight-scale invariance. The graph measure is invariant to a global scale factor for all edges: (Miyajima & Sakuragawa, 2014).

• Applicable to fully weighted networks. In some applications, it is beneficial to avoid any thresholding of the weights of the connections in a network. As a result, every node is connected with every other node, although the weights may be very small. A generalization of the clustering coefficient and the local efficiency should be applicable to such cases.

### 2.2  Generalizations

A good review of existing generalizations of the clustering coefficient and local efficiency can be found in Miyajima and Sakuragawa (2014). The authors investigated general versatility, weight-scale invariance, and continuity. Here, we investigate all criteria listed in the previous section. We first give a short description of the different generalizations currently available.

Barrat et al. (2004) proposed a generalization by including the node strength and the weights of the connections from node :
2.5
If the network is fully weighted, for all nodes .
Onnela et al. (2005) proposed a weighted clustering coefficient for node based on the weighted triangles, and this algorithm is used in the brain connectivity toolbox (Rubinov & Sporns, 2010):
2.6
Zhang and Horvath (2005) have defined, in their gene co-expression network analysis, a clustering coefficient for node for a fully weighted network. The original equation can be rewritten as (Saramäki et al., 2007):
2.7
Holme, Park, Kim, and Edling (2007) have defined a similar definition as the previous one except that in the denominator, is not required:
2.8
Opsahl and Panzarasa (2009) proposed a generalization as
2.9

They proposed four methods to calculate : arithmetic mean (), geometric mean (), and maximum () and minimum () of the weights of the edges. We refer to the set of these four methods by .

Miyajima and Sakuragawa (2014) extended the generalization of the cluster coefficient of node to the case of weighted directed networks using different functions (multiplication, geometric mean, minimum, and harmonic mean). The case of multiplication in the context of an undirected network leads to the same generalization as the one from Holme et al. (2007). For undirected networks, we give their other extensions below:

• Geometric mean:
2.10
• Minimum:
2.11
• Harmonic mean:
2.12
We refer to the set of these three methods by .

A generalization of the local efficiency is given by Rubinov and Sporns (2010):
2.13
in which is the subgraph consisting of the neighbors of excluding node itself, and is the shortest distance between nodes and containing only neighbors of . The distance between nodes and in a weighted network is defined as
2.14
with the shortest weighted path between and . If no path containing these neighbors is found, .

As is the case for the clustering coefficient, multiple generalizations can be defined for the weighted local efficiency. We define three possible extensions that we compare with the current generalization defined by Rubinov and Sporns (2010).

The first alternative for the weighted local efficiency is given by
2.15
where is the adapted shortest distance between and . This adapted shortest distance was calculated as the shortest distance in the network containing all neighbors of excluding node after replacing the weight of edge to :
2.16
If no path containing nodes and is found in , .

Weighting by makes the shortest distance invariant to the weight scale.

The second alternative for the weighted local efficiency is given by
2.17
and the third alternative, more closely related to the extension defined in equation 2.13 is
2.18
where is the adapted shortest distance between and . This adapted shortest distance was calculated as the shortest distance in the network containing all neighbors of excluding node after replacing the weight of edge to
2.19
If no path containing nodes and is found in , .

### 2.3  Application to Two Real-World Networks

A number of essential (general versatility, continuity) and useful (weight-scale invariance and applicability to fully weighted networks) properties are evaluated on a theoretical basis. The essential property sensitivity will be assessed by studying the cases shown in Figure 1, while the fourth essential property robustness to noise will be assessed using two real-world networks.

#### 2.3.1  The Associative-Semantic Network

An empirical network was taken to test the properties of the generalization. The associative-semantic network is constructed from functional interactions between brain regions activated during the associative-semantic task (Vandenberghe et al., 2013; Wang et al., 2014) measured using fMRI. The network has 57 nodes, which are mostly located in the left hemisphere. The data are taken from one elderly subject who participated in an fMRI measurement on a 3T Philips system (Wang et al., 2014). The nodes were defined based on a previous experiment (Vandenberghe et al., 2013). Based on the average time series in these nodes, partial correlations were calculated. The weight of the edge between node and is calculated from the Fisher r-to-z transform of the partial correlation as
2.20
where is the cumulative distribution function of the standard normal distribution. The weights are a measure of the functional interaction between brain regions.

We will evaluate the robustness to noise of the different generalizations by studying the situation in which we add noise to the -value (before the transformation to weights) of each (nonzero) connection using a standard normal distribution as noise model multiplied by some constant to model the amount of noise. After adding the noise, weights are calculated as before using equation 2.20. We will study the case of corresponding to different levels of noise ranging from weak to strong noise. The average error will be calculated over 10 noise realizations.

Since this is a fully weighted network, we will also calculate the correlation of the different versions of the clustering coefficient and local efficiency between this fully weighted network and the soft-thresholded network (thresholded such that the density is 80%, 60%, or 40%). Often a threshold is used to remove connections with low weight. This is referred to as the creation of soft-thresholded weighted networks. We hypothesize that weighted graph measures calculated for the original weighted network and for the soft-thresholded weighted network are highly correlated, especially when the density of the latter network is high.

#### 2.3.2  The Resting State fMRI Network

The second network is a functional connectivity network constructed from correlations between regional fMRI times series, measured in 638 nodal locations from 27 healthy volunteers scanned in resting state on a Siemens 3T scanner. The details of this experiment can be found in Crossley et al. (2013). The data of this network are publicly available.1 Unfortunately, the connection strengths (expressed as -scores) were already thresholded, and as a result, only the connections with were available. Therefore, we can only study the robustness to noise in this case. We will do this in the same way as the first real-world network, including the transformation of -values to weights using equation 2.20.

## 3  Results

### 3.1  General Versatility

All the generalizations of the clustering coefficient, except , lead to the same equation in the case of binary undirected networks, as can be easily seen from equations 2.5 to 2.7 and 2.9 to 2.12, where , 0 or 1 and . The generalization does not show general versatility because in the denominator, there is no requirement that the two sides of a triangle should be different (i.e., when the triplet is not a triangle but a line).

The generalization of the local efficiency, introduced in equation 2.13, does not show general versatility because of the power of the distance compared to in the binary case. In contrast, the generalizations of the local efficiency proposed in this letter—equations 2.15, 2.17, and 2.18—do show general versatility.

The results of each generalization for this criterion are summarized in Table 1.

Table 1:
General Versatility and Continuity for Fully Weighted Networks of the Different Generalizations.
MethodGeneral VersatilityContinuity
Yes No
Yes No
Yes Yes
No Yes
Yes No
Yes No
Yes No
Yes No
Yes Yes
Yes Yes
Yes Yes
No No
Yes Yes
Yes Yes
Yes Yes
MethodGeneral VersatilityContinuity
Yes No
Yes No
Yes Yes
No Yes
Yes No
Yes No
Yes No
Yes No
Yes Yes
Yes Yes
Yes Yes
No No
Yes Yes
Yes Yes
Yes Yes

### 3.2  Continuity

The node degree is a discontinuous function for a weighted network since any node with a nonzero weight is considered a neighbor irrespective of the amplitude. This implies that the value for the node degree will differ with 1 between the case in which an arbitrary small weight is present for an edge between nodes and and the case in which this edge is not present (i.e., has zero weight). As a result, , and are not continuous. is also not continuous since in the numerator, only closed triangles will contribute, no matter how small the weight of the third connection in the triangle is and the contribution depends only on the weights of the two other connections in the triangle. The other extensions—, and —are all continuous.

The results of each generalization for this criterion are summarized in Table 1.

### 3.3  Sensitivity

In Table 2, we show how far each generalization is able to detect differences between each of the six possible cases shown in Figure 1 for the clustering coefficient and the local efficiency. We have given a weak connection the value 0.1 and a strong connection the value 1 while assuming that .

Table 2:
Sensitivity of the Clustering Coefficient and Local Efficiency for the Cases Presented in Figure 1.
MethodNumber of Different Values (max = 6)MinimumMaximum

0.1
0.1
0.0165 0.5

0.3162
0.1
0.1818
0.1
0.0001
0.001
0.4642
MethodNumber of Different Values (max = 6)MinimumMaximum

0.1
0.1
0.0165 0.5

0.3162
0.1
0.1818
0.1
0.0001
0.001
0.4642

### 3.4  Robustness to Noise

When adding different amounts of gaussian noise to both real-world networks, we observe that the generalizations and of the clustering coefficient perform best for both networks across all levels of noise used in this study with a mean error within 5%. Most of the other generalizations also perform reasonably well, with mean errors within 10% (see Figure 2).

Figure 2:

Mean relative error of the robustness to noise of the clustering coefficient for different generalizations as a function of the amount of gaussian noise for the associative-semantic network (left) and the resting-state fMRI network (right) on the nonzero connections. The noise fraction is defined as the factor that is multiplied with samples from the standard normal noise distribution. In the left panel, the lines of and almost coincide, and this is also the case for , , and in the right panel.

Figure 2:

Mean relative error of the robustness to noise of the clustering coefficient for different generalizations as a function of the amount of gaussian noise for the associative-semantic network (left) and the resting-state fMRI network (right) on the nonzero connections. The noise fraction is defined as the factor that is multiplied with samples from the standard normal noise distribution. In the left panel, the lines of and almost coincide, and this is also the case for , , and in the right panel.

All generalizations of the local efficiency have an acceptable mean error (i.e., less than 5%) in both networks when noise is not too large (see Figure 3). However, when noise increases, only and have mean errors below 10% in both networks.

Figure 3:

Mean relative error of the robustness to noise of the local efficiency for different generalizations as a function of the amount of gaussian noise for the associative-semantic network (left) and the resting-state fMRI network (right). The noise fraction is defined as the factor that is multiplied with samples from the standard normal noise distribution.

Figure 3:

Mean relative error of the robustness to noise of the local efficiency for different generalizations as a function of the amount of gaussian noise for the associative-semantic network (left) and the resting-state fMRI network (right). The noise fraction is defined as the factor that is multiplied with samples from the standard normal noise distribution.

### 3.5  Weight-scale Invariance and Applicability to Fully Weighted Networks

Weight-scale invariance is satisfied for all generalizations of the clustering coefficient as can be derived mathematically by multiplying every weight by a factor and observing that the result is independent of this factor. The generalizations of the local efficiency , , and also show weight-scale invariance, but this is not the case for .

From equation 2.5 for and equation 2.9 for , we see that for fully weighted networks, the clustering coefficient equals 1 for all nodes, and therefore we consider these generalizations not suitable for fully weighted networks (see Table 3). All other generalizations for the clustering coefficient and the local efficiency can be used for fully weighted networks.

Table 3:
Weight Scale Invariance and Applicability to Fully Weighted Networks of the Different Generalizations.
MethodWeight Scale InvarianceSuitable for Fully Weighted Networks
Yes No
Yes Yes
Yes Yes
Yes Yes
Yes No
Yes No
Yes No
Yes No
Yes Yes
Yes Yes
Yes Yes
No Yes
Yes Yes
Yes Yes
Yes Yes
MethodWeight Scale InvarianceSuitable for Fully Weighted Networks
Yes No
Yes Yes
Yes Yes
Yes Yes
Yes No
Yes No
Yes No
Yes No
Yes Yes
Yes Yes
Yes Yes
No Yes
Yes Yes
Yes Yes
Yes Yes

A summary table with the main findings for the essential and useful properties is given in Table 4.

Table 4:
Summary of the Main Findings.
PropertyClustering CoefficientLocal Efficiency
General versatility , , , , , , ,
, , ,
Continuity , , , ,  , ,
Sensitivity , , , , , , , ,
, , , ,
Robustness to noise , , , , ,  , , ,
Weight scale invariance All generalizations , ,
Applicable to fully , , , , ,  All generalizations
weighted networks
PropertyClustering CoefficientLocal Efficiency
General versatility , , , , , , ,
, , ,
Continuity , , , ,  , ,
Sensitivity , , , , , , , ,
, , , ,
Robustness to noise , , , , ,  , , ,
Weight scale invariance All generalizations , ,
Applicable to fully , , , , ,  All generalizations
weighted networks

Note: The generalizations listed satisfy the property or are ranked according to performance.

Listed based on their overall ranking (see Table 2) from best to worst.

Listed based on their overall ranking (see Figures 2 and 3) from best to worst.

### 3.6  Soft-Thresholded Weighted Networks

For generalizations of the clustering coefficient that can be applied to fully weighted networks, we compared the values obtained in a fully weighted network with those obtained in a soft-threshold network. Since we have only unthresholded data for the associative-semantic network, the analysis is limited to this network. The hypothesis is that there will be a high correlation between both cases, especially when the density of the soft-thresholded network is high. In Figure 4 and Table 5, the results are shown for different soft-threshold values.

Figure 4:

Scatter plot of the nodal clustering coefficient for different generalizations for nodes in the fully weighted network and the soft-thresholded weighted associative-semantic network.

Figure 4:

Scatter plot of the nodal clustering coefficient for different generalizations for nodes in the fully weighted network and the soft-thresholded weighted associative-semantic network.

Table 5:
Correlation between the Clustering Coefficient or Local Efficiency Calculated in Each Node for the Fully Weighted Network and the Soft-Thresholded Weighted Network in the Associative-Semantic Network.
Density (%)406080
0.21 0.57 0.81
0.91 1.00 1.00
0.91 1.00 1.00
0.52 0.85 0.96
0.71 0.97 1.00
0.55 0.92 1.00
0.51 0.68 0.82
0.97 1.00 1.00
0.92 0.99 1.00
0.65 0.89 0.98
Density (%)406080
0.21 0.57 0.81
0.91 1.00 1.00
0.91 1.00 1.00
0.52 0.85 0.96
0.71 0.97 1.00
0.55 0.92 1.00
0.51 0.68 0.82
0.97 1.00 1.00
0.92 0.99 1.00
0.65 0.89 0.98

Second, we performed the same analysis for the generalizations of the local efficiency. The results are shown in Figure 5 and Table 5.

Figure 5:

Scatter plot of the nodal local efficiency for different generalizations for nodes in the fully weighted network and the soft-thresholded weighted associative-semantic network.

Figure 5:

Scatter plot of the nodal local efficiency for different generalizations for nodes in the fully weighted network and the soft-thresholded weighted associative-semantic network.

## 4  Discussion

In this letter, we have defined a set of essential and useful properties that should ideally be satisfied for a generalization of a graph measure when extending from a binary network to a (fully) weighted network. We have compared all of these properties for the generalizations for the clustering coefficient and the local efficiency found in the literature, as well as for new generalizations. Some of the generalizations are especially suited in the case of (fully) weighted undirected graphs.

### 4.1  Essential Properties of Generalizations of Binary Graph Measures

Generalizations from binary graph measures that are applicable to (fully) weighted graphs should ideally satisfy a number of properties. These properties can be subdivided into essential properties and useful properties. The latter class of properties depends on the application and should be considered relevant only in those applications.

The first essential property is general versatility, which refers to the fact that when applying the generalization on a binary graph, the result should be the same as the corresponding binary graph measure. This property is not satisfied for the generalization of the clustering coefficient and the generalization of the local efficiency. The second essential property is continuity, which means that an infinitesimal small change in one of the weights should lead to an infinitesimal small change in the graph measure. This is not the case for , , and , and it is also not satisfied for . Important to note is that expressions for the local clustering coefficient (see equation 2.6) and the local efficiency (see equation 2.13), currently used in the brain connectivity toolbox in case of weighted undirected graphs, are not satisfying continuity (Onnela et al., 2005; Rubinov & Sporns, 2010). The third essential property is sensitivity to capture different cases for which the graph measures are designed. We have evaluated this property by looking at six possible cases for a simple triangle since both clustering coefficient and local efficiency are based on triangles. We found that the most sensitive generalizations for the clustering coefficient are , , , and , which could distinguish four of six cases. The best generalizations for the local efficiency are and , which were able to distinguish five of six cases. The fourth essential property is robustness to noise. We have investigated the robustness against different amounts of gaussian noise for two different real-world networks of different sizes. We found that and were the most robust generalizations for the clustering coefficient and and are the most robust generalizations for the local efficiency.

### 4.2  Useful Properties of Generalizations of Binary Graph Measures

Weight-scale invariance means that the graph measure is invariant to a global scale factor for all edges. In some cases, only relative connection strengths can be determined, and this property is especially useful in such cases. All generalizations of the clustering coefficient and the local efficiency are weight-scale-invariant except the generalization for the local efficiency. Furthermore, all generalizations of the local efficiency can be applied to fully weighted networks. This is also the case for most generatlizations of the clustering coefficient except for and .

### 4.3  Fully Weighted Undirected Graphs

Most studies on graphs in neuroscience are related to binary undirected graphs (Sporns, Honey, & Kötter, 2007; He et al., 2007; He, Chen, & Evans, 2008; Van Wijk, Stam, & Daffertshofer, 2010; Vandenberghe et al., 2013). These graphs have either a connection or not between a pair of nodes, and they are easy to analyze. However, in order to obtain a binary graph, some measure of connectivity (often continuous) between nodes needs to be calculated and then thresholded on either amplitude or significance. The results of this procedure critically depend on the threshold used and do not take into account the strength of the connection. As a result, true connections that do not survive the threshold are removed, while false connections may sometimes be included. An alternative is the use of weighted graphs. In order to avoid taking into account spurious noisy connections, a soft threshold is sometimes applied, which removes these connections. The other connections are weighted (Wang, Li, Metzak, He, & Woodward, 2010; van den Heuvel, Mandl, Stam, Kahn, & Pol, 2010). This reduces the problem described above but does not solve it completely. The advantage of fully weighted graphs is that no thresholding is required and all connections are taken into account (Mumford et al., 2010). The weight should then reflect not only the strength of the actual underlying biological connection but also the probability of being a true connection. Therefore, it might be necessary to apply a transformation from connection strength (e.g., defined by the (partial) correlation between two nodes in fMRI based functional networks) to weights. In case of the associative-semantic network, we have shown that the generalizations that are applicable to fully weighted networks show a high correlation with the network, which is soft-thresholded, especially when the density of the latter is high.

### 4.4  Choice of the Best Generalization

The choice of the best generalization is not always easy. The essential requirements of general versatility and continuity can be proven mathematically, and they are completely independent of the application. The relative importance of the two other essential properties, sensitivity and robustness to noise, depend on the application and most likely requires a trade-off between these two properties. In this study, we have tried to quantify sensitivity based on the values obtained for six possible triangles and robustness to noise by evaluating the behavior when adding different amounts of gaussian noise. Based on our results, we propose that the best generalization of the clustering coefficient is , which is more robust to noise compared to . The choice of the best generalization of the local efficiency is , but if robustness to noise is very important, can be selected; sensitivity, however, will clearly be lower compared to . If the noise in an application is nongaussian, a similar approach, as we have shown, can be taken for the noise model, which is more appropriate for the application. Satisfying the useful properties can be important but depends on the application. Despite the difficulty in selecting the optimal generalization, we believe that readers can use the assessment of all properties for all generalizations to a select the best generalization for the application under study.

## 5  Conclusion

In this letter, we have focused on the comparison of different generalizations for the clustering coefficient and local efficiency to the case of (fully) weighted networks by looking at different properties of these graph measures and studying the performance in two real-world networks of different sizes. The best generalization of the clustering coefficient is , defined in Miyajima and Sakuragawa (2014), while the best generalization of the local efficiency is proposed in our work. Depending on the application and the relative importance of sensitivity and robustness to noise, other generalizations may be selected on the basis of the properties investigated in this letter.

## Acknowledgments

This work was supported by Research Foundation Flanders (FWO; G0660.09 and G0A0913N to R.V. and P.D.), KU Leuven (OT/12/097 to R.V. and P.D.), Federaal Wetenschapsbeleid belspo (IAP-VII P7/11), and Stichting voor Alzheimer Onderzoek (SAO11020 and 13007). Y.W. has a grant from the Chinese Scholarship Council, and R.V. is a senior clinical investigator. We thank both reviewers for their constructive comments, which greatly improved the letter.

## References

Achard
,
S.
, &
Bullmore
,
E.
(
2007
).
Efficiency and cost of economical brain functional networks
.
PLoS Computational Biology
,
3
(
2
),
e17
.
Amaral
,
L. A.
, &
Ottino
,
J. M.
(
2004
).
Complex networks
.
European Physical Journal B—Condensed Matter and Complex Systems
,
38
,
147
162
.
Barabasi
,
A.-L.
, &
Oltvai
,
Z. N.
(
2004
).
Network biology: Understanding the cell’s functional organization
.
Nature Reviews Genetics
,
5
,
101
113
.
Barrat
,
A.
,
Barthelemy
,
M.
,
Pastor-Satorras
,
R.
, &
Vespignani
,
A.
(
2004
).
The architecture of complex weighted networks
.
Proceedings of the National Academy of Sciences of the United States of America
,
101
,
3747
3752
.
Batalle
,
D.
,
Eixarch
,
E.
,
Figueras
,
F.
,
Muñoz-Moreno
,
E.
,
Bargallo
,
N.
,
Illa
,
M.
, …
Gratacos
,
E.
(
2012
).
Altered small-world topology of structural brain networks in infants with intrauterine growth restriction and its association with later neurodevelopmental outcome
.
NeuroImage
,
60
,
1352
1366
.
Bullmore
,
E.
, &
Sporns
,
O.
(
2009
).
Complex brain networks: Graph theoretical analysis of structural and functional systems
.
Nat. Rev. Neurosci.
,
10
,
186
198
.
Crossley
N. A.
,
Mechelli
,
A.
,
Vrtes
,
P. E.
,
Winton-Brown
,
T. T.
,
Patel
,
A. X.
,
Ginestet
,
C. E.
, …
Bullmore
,
E. T.
(
2013
).
Cognitive relevance of the community structure of the human brain functional coactivation network
.
,
110
,
11583
11588
.
Fornito
,
A.
,
Zalesky
,
A.
, &
Breakspear
,
M.
(
2013
).
Graph analysis of the human connectome: Promise, progress, and pitfalls
.
NeuroImage
,
80
,
426
444
.
He
,
Y.
,
Chen
,
Z. J.
, &
Evans
,
A. C.
(
2007
).
Small-world anatomical networks in the human brain revealed by cortical thickness from MRI
.
Cereb. Cortex
,
17
(
10
),
2407
2419
.
He
,
Y.
,
Chen
,
Z.
, &
Evans
,
A.
(
2008
).
Structural insights into aberrant topological patterns of large-scale cortical networks in Alzheimer’s disease
.
Journal of Neuroscience
,
28
,
4756
4766
.
Holme
,
P.
,
Park
,
S. M.
,
Kim
,
B. J.
, &
Edling
,
C. R.
(
2007
).
Korean university life in a network perspective: Dynamics of a large affiliation network
.
Physica A: Statistical Mechanics and Its Applications
,
373
,
821
830
.
Latora
,
V.
, &
Marchiori
,
M.
(
2003
).
Economic small-world behavior in weighted networks
.
European Physical Journal B—Condensed Matter and Complex Systems
,
32
,
249
263
.
Miyajima
,
K.
, &
Sakuragawa
,
T.
(
2014
).
Continuous and robust clustering coefficients for weighted and directed networks.
arXiv:1412.0059
Mumford
,
J. A.
,
Horvath
,
S.
,
Oldham
,
M. C.
,
Langfelder
,
P.
,
Geschwind
,
D. H.
, &
Poldrack
,
R. A.
(
2010
).
Detecting network modules in fMRI time series: A weighted network analysis approach
.
NeuroImage
,
52
,
1465
1476
.
Onnela
,
J.-P.
,
Saramäki
,
J.
,
Kertész
,
J.
, &
,
K.
(
2005
).
Intensity and coherence of motifs in weighted complex networks
.
Phys. Rev. E
,
71
,
065103
.
Opsahl
,
T.
, &
Panzarasa
,
P.
(
2009
).
Clustering in weighted networks
.
Social Networks
,
31
,
155
163
.
Rubinov
,
M.
, &
Sporns
,
O.
(
2010
).
Complex network measures of brain connectivity: Uses and interpretations
.
NeuroImage
,
52
,
1059
1069
.
Saramäki
,
J.
,
Kivelä
,
M.
,
Onnela
,
J.-P.
,
,
K.
, &
Kertesz
,
J.
(
2007
).
Generalizations of the clustering coefficient to weighted complex networks
.
Physical Review E
,
75
,
027105
.
Sporns
,
O.
,
Honey
,
C. J.
, &
Kötter
,
R.
(
2007
).
Identification and classification of hubs in brain networks
.
PloS One
,
2
(
10
),
e1049
.
van den Heuvel
,
M. P.
,
Mandl
,
R. C.
,
Stam
,
C. J.
,
Kahn
,
R. S.
, &
Pol
,
H. E. H.
(
2010
).
Aberrant frontal and temporal complex network structure in schizophrenia: A graph theoretical analysis
.
Journal of Neuroscience
,
30
(
47
),
15915
15926
.
Van Wijk
,
B. C.
,
Stam
,
C. J.
, &
Daffertshofer
,
A.
(
2010
).
Comparing brain networks of different size and connectivity density using graph theory
.
PLoS One
,
5
(
10
),
e13701
.
Vandenberghe
,
R.
,
Wang
,
Y.
,
Nelissen
,
N.
,
Vandenbulcke
,
M.
,
Dhollander
,
T.
,
Sunaert
,
S.
, &
Dupont
,
P.
(
2013
).
The associative-semantic network for words and pictures: Effective connectivity and graph analysis
.
Brain Lang.
,
127
(
2
),
264
272
.
Wang
,
L.
,
Li
,
Y.
,
Metzak
,
P.
,
He
,
Y.
, &
Woodward
,
T. S.
(
2010
).
Age-related changes in topological patterns of large-scale brain functional networks during memory encoding and recognition
.
NeuroImage
,
50
,
862
872
.
Wang
,
Y.
,
Nelissen
,
N.
,
,
K.
,
De Weer
,
A.-S.
,
Vandenbulcke
,
M.
,
Sunaert
,
S.
, …
Dupont
,
P.
(
2014
).
Reproducibility and robustness of graph measures of the associative-semantic network
.
PloS One
,
9
(
12
),
e115215
.
Watts
,
D. J.
, &
Strogatz
,
S. H.
(
1998
).
Collective dynamics of small-world networks
.
Nature
,
393
(
6684
),
440
442
.
Zhang
,
B.
, &
Horvath
,
S.
(
2005
).
A general framework for weighted gene co-expression network analysis
.
Statistical Applications in Genetics and Molecular Biology
,
4
(
1
),
1
43
.

1


text:
# Kerodon

$\Newextarrow{\xRightarrow}{5,5}{0x21D2}$ $\newcommand\empty{}$

Remark 6.3.1.17. Let $F: \operatorname{\mathcal{C}}\rightarrow \operatorname{\mathcal{D}}$ be a morphism of simplicial sets which exhibits $\operatorname{\mathcal{D}}$ as a localization of $\operatorname{\mathcal{C}}$ with respect to a collection of edges $W$. Let $[W]$ denote the collection of morphisms in the homotopy category $\mathrm{h} \mathit{\operatorname{\mathcal{C}}}$ which belong to the image of $W$. Then the induced functor $\mathrm{h} \mathit{F}: \mathrm{h} \mathit{\operatorname{\mathcal{C}}} \rightarrow \mathrm{h} \mathit{\operatorname{\mathcal{D}}}$ exhibits the homotopy category $\mathrm{h} \mathit{\operatorname{\mathcal{D}}}$ as a $1$-categorical localization of $\mathrm{h} \mathit{\operatorname{\mathcal{C}}}$ with respect to $[W]$, in the sense of Definition 6.3.0.6. This follows immediately from Example 6.3.1.6.